[BOJ/Python] 백준 2828번 - 사과 담기 게임 풀이

📣코딩테스트를 위한 백준 문제 추천 모음

문제

백준 2828번 - 사과 담기 게임

문제 정의

위에서 사과가 떨어지면 밑에서 바구니로 사과를 받는 오락실 게임이다. 총 스크린 크기와 바구니 크기 사과가 떨어지는 좌표는 각각 입력값으로 주어지며 바구니는 항상 제일 왼쪽에서 시작한다고 한다. 이때 사과를 받기 위해 바구니를 최소한 몇 번을 이동해야 하는지 구하는 문제이다.

예를 들어 총 스크린 크기가 5, 바구니 크기가 2, 사과가 순서대로 1, 5, 3으로 떨어진다면 처음 사과는 움직이지 않고 받을 수 있으며 두 번째 사과는 오른쪽으로 3칸 마지막 사과는 왼쪽으로 한 칸 총 4칸을 이동해야 한다.

접근 방법

이 문제는 그리디 문제이면서 구현 문제이기도 하다. 사과를 떨어지는 순서대로 받아야 하므로 입력값대로 움직이면 항상 최적의 해를 가질 수 있다.

이런 무언가를 옮기는 문제는 바구니의 크기에 따라 맨 처음을 start, 마지막을 end로 좌표처럼 설정하고 움직인 만큼 좌표 이동시키는 방법이 문제를 해결하기 쉽다!

문제 해설

접근 방법에서 설명한 대로 바구니 크기대로 항상 시작은 왼쪽이므로 start는 1 end는 바구니 크기인 m으로 설정한다. 그다음 떨어지는 사과의 개수만큼 반복문을 돌려 사과가 떨어지는 순서대로 세 가지 케이스로 검사를 한다.

만약 떨어진 사과가 start보다 작다면 바구니 왼쪽에 사과가 떨어진 것이므로 바구니를 start - 떨어진 사과 좌표 만큼 왼쪽으로 이동시키고 떨어진 사과가 end 보다 크다면 바구니 오른쪽에 사과가 떨어진 것이므로 바구니를 떨어진 사과 좌표 - end만큼 오른쪽으로 이동시키고 떨어진 사과가 start와 end 사이에 있다면 바구니에 자연스럽게 담길 수 있기 때문에 이동할 필요가 없다.

풀이

import sys
input = sys.stdin.readline

def sol(start, end, apples):
    distance = 0

    for apple in apples:
        if(end < apple):
            (start, end, distance) = map(lambda x: x + apple - end, (start, end, distance))
        elif(apple < start):
            distance += start - apple
            (start, end) = map(lambda x: x - (start - apple), (start, end))
        else:
            continue

    return distance

if __name__ == '__main__':
    n, m = map(int, input().split())
    num = int(input())
    apples = list(int(input()) for _ in range(num))

    start = 1
    end = m

    print(sol(start, end, apples))

정리

이번 문제는 문제에서 순서대로 받는다고 명시되어 있어 항상 최적의 해를 가지기 때문에 딱히 검사할 필요가 없이 입력값 순서대로 풀면 되는 쉬운 문제였다. 풀이의 시간 복잡도는 O(N)이고 시간제한이 1초이므로 시간 복잡도는 생각하지 않고 문제를 풀었다.

⚡직접 문제를 풀어보고 작성한 글입니다.⚡
🙂틀린 부분이나 보완할 점이 있을 경우 언제든지 댓글 혹은 메일로 지적해 주시면 감사하겠습니다!🙂