[구현/그리디] 백준 2828 사과 담기 게임 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2828번: 사과 담기 게임

 

 

 

2. 문제 풀이

 떨어지는 사과를 바구니로 받는 게임에서 최소의 이동거리로 바구니를 움직여야 합니다. 스크린의 길이는 N칸이고, 바구니의 너비는 M칸입니다. 최초 시작 시 바구니가 맨 왼쪽에 위치한다면, 총 얼마만큼 움직여야 하는지 구해야 합니다.

 

 

 그리디 알고리즘을 사용합니다. 최소의 움직임으로 사과를 받으려면 바구니의 양쪽 끝에서 받아야 합니다. (여기서 m은 편의상 m-1입니다.) 예를 들어 바구니의 너비가 2이고, 1~2 위치에서 위치 5의 사과를 받으려면 4~5 위치로 이동해야 합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n, m = map(int, input().split())  # 스크린의 길이, 바구니 너비
m -= 1
j = int(input())

# 그리디
res = 0  # 바구니가 이동해야 하는 최소 거리
loc = 1  # 바구니의 왼쪽 끝 위치
for _ in range(j):
    x = int(input())

    # 바구니보다 왼쪽에 있을 경우
    if x < loc:
        res += (loc - x)
        loc = x

    # 바구니에 위치할 경우
    elif loc <= x < loc+m:
        pass  # 가만히 있음

    # 바구니보다 오른쪽에 있을 경우
    else:
        res += (x-m) - loc
        loc = x-m
print(res)

 맨 왼쪽 끝을 '바구니의 위치'로 잡고, 움직여야 하는 방향을 계산합니다. 만약 사과가 바구니보다 왼쪽에 있을 경우, 사과 위치로 바구니 왼쪽 끝을 이동시킵니다. 반대로 사과가 바구니보다 오른쪽에 있을 경우에는 사과 위치로 바구니 오른쪽 끝을 이동시킵니다. 마지막으로 사과가 바구니 위에 떨어진다면, 움직이지 않습니다.