[그리디/백준] 2828번: 사과 담기 게임

-문제 : https://www.acmicpc.net/problem/2828

 

스스로 푼 문제이고, Silver Level 5 문제

 

-정답풀이 :

바구니의 크기에 커짐에 따라 크게 안 움직여도 된다. 바구니가 위치한 범위 내에 사과가 떨어지면 되므로 바구니의 움직임이 최소가 되려면 왼쪽 끝과 오른쪽 끝을 생각하면서 진행하면 된다. 

 

apple이 바구니보다 왼쪽에 있으면 바구니의 왼쪽 끝, apple이 바구니보다 오른쪽에 있으면 바구니의 오른쪽 끝을 움직이고, 각 끝이 움직인 거리를 answer에 더해주면 된다.

 

주의할 거는 각 끝부분도 바구니의 일부분이므로 current 위치 변경할 때 m을 가지고 연산하는 것이 아닌 m-1로 연산해야한다 

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
j=int(input())
apples=[]
for _ in range(j):
    apples.append(int(input()))
answer=0
current=[1,m]
if m==1:
    for i in range(1,j):
        answer+=abs(apples[i]-apples[i-1])
    print(answer)
else:
    for i in range(j):
        if apples[i]>current[1]:
            answer+=(apples[i]-current[1])
            current[0]=apples[i]-(m-1)
            current[1]=apples[i]
        elif apples[i]<current[0]:
            answer+=(current[0]-apples[i])
            current[0]=apples[i]
            current[1]=apples[i]+(m-1)
    print(answer)