[baekjoon/python]2828 - 그리디,구현
[Silver V] 사과 담기 게임 - 2828
성능 요약
메모리: 31120 KB, 시간: 40 ms
분류
그리디 알고리즘, 구현
제출 일자
2024년 3월 10일 21:50:37
문제 설명
상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M 스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다. 바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오. 첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다. 모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다. 처음에 접근할때는 리스트를 생성해서 현재 발판이 존재하는 위치를 전부 원소로 표시하려고 했으나 결국 중요한 부분은 예를 들어 발판을 기준으로 오른쪽으로 이동하는 경우에 가장 오른쪽의 발판 위치만 신경쓰면 된다는 것이였다. 즉 경우의 수는 사과가 등장했을때, 다른 풀이법을 찾아봤는데 readline 대신 input으로 받아 append한 리스트를 쓰는 입력방식의 차이말고는 딱히 크게 없었다.입력
출력
회고
from sys import stdin as s
# import os
# print(os.getcwd())
# s = open("input.txt") #제출시에는 해당라인 주석처리
N, M = map(int, s.readline().split())
V = int(s.readline())
result = 0
min = 1
max = M
for _ in range(V):
apple_pos = int(s.readline())
if min<=apple_pos<=max:
result+=0 #반응없음
elif apple_pos<min:
move=min-apple_pos
min-=move
max-=move
result+=move
elif max<apple_pos:
move=apple_pos-max
min+=move
max+=move
result+=move
print(result)
그래서 발판의 가장 오른쪽 위치를 max로 가장 왼쪽을 min으로 설정하였다.
그 후 이동하는 거리만큼 max와 min을 최신화해주면 이동 거리의 최솟값을 구할 수 있었다.