문제
N칸 화면에 M칸 바구니로 떨어지는 사과를 받을 때, 바구니의 최소 이동 거리를 구하라.
입력
화면 크기 N, 바구니 크기 M, 사과 수 J와 각 사과의 위치가 주어진다.
출력
최소 이동 거리를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 1 3 1 5 3 | 6 |
풀이
사과 위치에 맞춰 바구니를 최소한으로 이동한다.
- 사과가 바구니 범위 안이면 이동하지 않는다
- 바구니보다 왼쪽이면 왼쪽으로 최소 이동한다
- 바구니보다 오른쪽이면 오른쪽으로 최소 이동한다
핵심 아이디어: 각 사과마다 바구니 범위에 포함시키는 최소 이동만 하면 총 이동이 최소화된다.
코드
import sys
N, M = map(int, sys.stdin.readline().split())
J = int(sys.stdin.readline())
now = 1
apples = []
answer = 0
for _ in range(J):
apples.append(int(sys.stdin.readline()))
for apple in apples:
if now <= apple and now + (M - 1) >= apple:
pass
elif now > apple:
answer += abs(apple - now)
now = apple
else:
answer += apple - (M - 1) - now
now = apple - (M - 1)
print(answer)복잡도
- 시간: O(N)
- 공간: O(N)