[Python] 2828번 사과 담기 게임

✏️ 문제

 

문제 파악

처음에는 현재 위치를 기준으로 현재 위치가 중간에 있으면 앞뒤로 (현재위치-길이/2)부터 (현재위치+길이/2)까지 사과가 떨어지는 위치에 해당되면 거리를 더하지 않고 해당되지 않으면 거리를 더하고 이런 방식으로 코드를 짜려고 했다. 

 

근데 하다보니 복잡하고 경우의 수가 너무 많은 것 같아서 결국 포기..

 

바구니의 왼쪽 위치와 오른쪽 위치를 저장해두고

1. 바구니의 왼쪽 위치보다 사과의 위치가 작으면 이동거리 = (바구니의 왼쪽 위치 - 사과의 위치)
2. 바구니의 오른쪽 위치보다 사과의 위치가 크면 이동거리 = (사과의 위치 - 바구니의 오른쪽 위치)
3. 그 외의 경우는 가만히 있어도 바구니 위치에 사과의 위치가 해당 (들어옴)

라고 푸는 게 훨 편했다..

 

알고리즘

• 그리디 알고리즘
• 구현

 

 

코드

n,m = map(int, input().split())
j = int(input())
 
left = 1
right = m
count = 0
 
for i in range(j):
    position = int(input())
 
    if left > position:
        count += (left - position)
        right -= (left - position)
        left = position
    elif right < position:
        count += (position - right)
        left += (position - right)
        right = position
 
print(count)