파이썬 그리디 알고리즘 백준 2828 사과 담기 게임

문제

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

출력

모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

풀이

모든 사과를 담기 위한 바구니의 최소 이동거리를 구해야 한다.

바구니의 시작 위치는 가장 왼쪽이고 바구니의 크기는 사용자 입력을 받는다.

따라서 바구니의 초기 left는 1, right는 1+입력받은 size이다.

이 left와 right를 가지고 떨어지는 사과의 위치와 비교해서 최소거리로 이동하면 된다.

사과의 위치가 right보다 크다면 더 왼쪽에 있는 것으로 right와의 차이만큼 왼쪽으로 이동하고,

사과의 위치가 left보다 작다면 더 오른쪽에 있는 것으로 left와의 차이만큼 오른쪽으로 이동한다.

각 이동에 따라 left, right 값을 갱신해주고, 움직인 거리만큼 count를 더해주면 된다.

 

import sys
n, m = map(int, sys.stdin.readline().rstrip("\n").split())
j = int(sys.stdin.readline().rstrip("\n"))
nums=[]
for i in range(j):
    nums.append(int(sys.stdin.readline().rstrip("\n")))
count=0
size=m-1
left=1
right = left+size
for i in range(len(nums)):
    if(left<=nums[i] and nums[i]<=right):
        continue
    if(nums[i]>right):
        temp = abs(nums[i]-right)
        count+=temp
        right+=temp
        left+=temp
    if(nums[i]<left):
        temp = abs(nums[i]-left)
        count+=temp
        left-=temp
        right-=temp


print(count)