🍜Problem
https://www.acmicpc.net/problem/18185
총 N개의 라면 공장이 있고 N(i)의 공장에서 꼭 A(i)개의 라면을 구매해야 한다.
라면을 구매하는 방법은 3가지가 있다.
1. i번째 공장에서 하나의 라면을 구매 (3원)
2. i번째 공장과 i + 1번째 공장에서 라면을 하나씩 구매 (5원)
3. i번째 공장과 i + 1번째 공장, i + 2번째 공장에서 라면을 하나씩 구매 (7원)
문제에 주어진 라면을 모두 구매할 때 돈을 최소로 지불하는 경우의 금액을 구해야 한다.
Solution
돈을 최소로 지불하는 가장 좋은 방법은 한 번에 최대한 많은 라면을 사는 것이다. 등차수열이므로 1개를 구매하는 것보다 2개 혹은 3개를 묶어서 구매하는 경우가 좋다.
맨처음에는 i, i + 1, i + 2를 비교해서 라면을 구매해야하는 최솟값을 찾아서 무조건 3개를 구매하도록 코드를 작성했다.
반례 찾기
입력값이 [1, 2, 1, 1]인 경우에는 0번째에서 2번째까지 3개를 묶어서 구매한다면 [0, 1, 0, 1]이 되고 남은 두 개의 라면은 각각 하나씩 구매해야 한다. 하지만 0번째에서 1번째까지 1개씩 구매한다면 [0, 1, 1, 1]이 되고 다시 1번째에서 3번째까지 1개씩 라면을 구매해서 더 적은 돈을 지불하고 모든 라면을 구매할 수 있게 된다.
반례에 대응해서 구현하기
최적의 구매 순서로 구매하도록 구현이 필요하다. i + 1값이 i + 2값보다 큰 경우 3묶음을 먼저 구매해버리면 i + 2의 라면을 혼자 구매해야하는 경우가 생기고 이렇게 되면 최적의 해를 구할 수 없게 된다.
먼저, i + 1번째 값과 i + 2번째 값을 비교하고 i + 1번째 값이 더 큰 경우에는 i + 2번째 값과 차이가 나는 만큼 먼저 2묶음을 구매하게 한다. 다음으로 i번째 값부터 i + 2번째 값까지 3묶음으로 구매할 수 있는 만큼 구매하고, i에 구매해야할 라면이 더 남았다면 단독으로 구매한다.
i + 2번째 값이 더 큰 경우에는 i번째부터 i + 2번째까지 3묶음으로 먼저 구매하고, i번째 부터 i + 1번째까지 2묶음으로 구매가 가능한 경우에 구매한다.
Python Code
from sys import stdin
N = int(stdin.readline())
A = list(map(int, stdin.readline().split())) + [0, 0]
answer = 0
for i in range(N):
if A[i + 1] > A[i + 2]:
min_A = min(A[i], A[i + 1] - A[i + 2])
answer += min_A * 5
A[i + 1] -= min_A
A[i] -= min_A
min_A = min(A[i], min(A[i + 1], A[i + 2]))
answer += min_A * 7
A[i + 2] -= min_A
A[i + 1] -= min_A
A[i] -= min_A
else:
min_A = min(A[i], min(A[i + 1], A[i + 2]))
answer += min_A * 7
A[i + 2] -= min_A
A[i + 1] -= min_A
A[i] -= min_A
min_A = min(A[i], A[i + 1])
answer += min_A * 5
A[i + 1] -= min_A
A[i] -= min_A
answer += 3 * A[i]
print(answer)
- 조건문을 작성할 때
i + 2번째 공장이 존재하지 않는 경우를 나눠서 구하지 않기 위해서A에[0, 0]을 덧붙여주었다.
