[BOJ] 2828. 사과 담기 게임

Python3

문제

https://www.acmicpc.net/problem/2828

키워드

• 그리디

문제 풀이

문제 요구사항

• 스크린은 N칸으로 나누어져 있다.
• 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N)
• 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. (경계는 넘어갈 수 x)
• 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.
• 스크린의 위에서 사과 여러 개가 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.
  => 입력받는 순서대로 이동을 해야 한다.
• 바구니의 이동 거리의 최솟값을 구하는 프로그램

변수 및 함수 설명

• n: 스크린 개수
• m: 바구니 칸 개수 (1 ≤ M < N ≤ 10)
• j: 사과가 떨어지는 개수 (1 ≤ J ≤ 20)
• left: 바구니의 시작이 위치한 칸
• right: 바구니의 끝이 위치한 칸
• cnt: 바구니의 이동 거리
• pos: 사과가 떨어지는 위치

풀이

포인트 (세 가지 경우로 나누어 생각)
1. 서 있는 위치에서 사과가 떨어져 움직일 필요가 없을 때 => continue
2. 서 있는 위치보다 왼쪽에서 떨어질 때 => 바구니 시작점에서 사과가 떨어지는 위치만큼 이동해야 한다.
3. 서 있는 위치보다 오른쪽에서 떨어질 때 => 사과가 떨어지는 위치에서 바구니 끝점만큼 이동해야 한다.

(입력 및 선언)

• 스크린 개수(n), 바구니 칸 개수(m), 사과가 떨어지는 개수(j)를 입력받는다.
• 바구니 시작 칸(left)은 1, 끝 칸(right)은 m이다.
  => right에 m을 대입하는 이유는 바구니 크기에 따라서 이동해야 하는 정도가 달라지기 때문이다. 바구니 크기(m)이 1이라면, 1에서 5까지는 4번 이동해야 하지만 2라면, 3번만 이동하면 된다.
• 바구니의 총 이동 거리는 0으로 초기화한다.

(반복문)

• 사과가 떨어지는 위치(pos)를 입력받는다.
• 사과가 바구니 안으로 쏙 들어가는 위치면 continue 한다. (셀 필요 없음)
• 만약 서 있는 곳보다 왼쪽에서 사과가 떨어지면,
• • (left-pos)만큼 이동해야 한다.
  • 이동하고 나면 바구니의 끝점(right)은 (left-pos)로 바뀐다.
  • 바구니의 시작점(left)는 사과가 떨어진 위치와 같다.
• 만약 오른쪽에 사과가 떨어지면,
• • (pos-right)만큼 이동해야 한다.
  • 이동 후 바구니의 시작점은 (pos-right)로 바뀐다.
  • 바구니의 끝점은 사과가 떨어진 위치와 같다.

최종 코드

n, m = map(int, input().split())
j = int(input())

left = 1
right = m
cnt = 0

for _ in range(j):
    pos = int(input())
    
    if left <= pos and pos <= right:
        continue
    elif pos < left:
        cnt += left-pos
        right -= left-pos
        left = pos
    else:
        cnt += pos-right
        left += pos-right
        right = pos

print(cnt)