[백준][Python] 2828 사과 담기 게임

구현, 그리디 / 실버 5

🍏

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

2828번: 사과 담기 게임

 

 

내 풀이

N, M = map(int, input().split())
apple = []
s = 0
e = M-1
ans = 0

J = int(input())
for _ in range(J):
    apple.append(int(input()))

for i in apple:
    if s <= i - 1 <= e:
        continue
    elif e < i - 1:
        ans += i - 1 - e
        e = i - 1
        s = e - (M - 1)
    elif s > i - 1:
        ans += s - (i - 1)
        s = i - 1
        e = s + M - 1

print(ans)

 

 

코드 설명

 

 

apple: 사과가 떨어지는 위치를 저장하는 리스트

s: 바구니의 시작 위치

e: 바구니의 끝 위치

 

🍏사과의 위치🍏

 

1. 사과가 바구니 안에 떨어지는 경우

바구니를 움직일 필요가 없으므로 다음 사과를 검사한다.

if s <= i - 1 <= e:
    continue

 

2. 사과가 바구니 오른쪽으로 떨어지는 경우

바구니의 끝 위치가 사과가 떨어지는 위치와 일치하기 위해 이동해야 하는 거리를 정답 변수에 더해준다.

그에 따라 바구니의 시작 위치와 끝 위치를 조정한다.

elif e < i - 1:
    ans += i - 1 - e
    e = i - 1
    s = e - (M - 1)

 

3. 사과가 바구니 왼쪽으로 떨어지는 경우

바구니의 시작 위치가 사과가 떨어지는 위치와 일치하기 위해 이동해야 하는 거리를 정답 변수에 더해준다.

그에 따라 바구니의 시작 위치와 끝 위치를 조정한다.

elif s > i - 1:
    ans += s - (i - 1)
    s = i - 1
    e = s + M - 1

 

2, 3번과 같은 작업을 진행하는 이유는 바구니가 최소 거리를 이동해야 하기 때문이다!