▶18185 - 라면 사기 (Small)
▶문제
라면마니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).
교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.
- i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
- i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.
- i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다.
최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.
▶입력
첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N가 주어진다.
두 번째 줄에 N개의 정수 A1, ···, AN가 사이에 공백을 두고 주어진다.
▶출력
첫 번째 줄에 교준이가 필요한 최소 금액을 출력한다.
▶풀이
단순히 3개짜리를 가장 많이 사고, 그다음 2개짜리를 사고 하는 방식은 이번문제에서 통하지 않는다.
예를 들어 1211이 있다고 가정하자.
제일 처음에 3개짜리를 구매할 수 있다.
그럼 0101이 되고, 1개짜리를 2번 구매해야 한다.
이렇게 해버리면 7 + 3 + 3 = 13이 된다.
하지만 처음에 2개를 구매하고 다음에 3개를 구매하면 5 + 7 = 12가 돼서 최소 금액이 된다.
이처럼 2번째와 3번째의 수를 비교해 보고 다르게 조건을 걸어주어야 한다.
만약 2번째가 3번째보다 크다면, 먼저 2개짜리를 구매해 주고,
나중에 3개짜리를 구매하면 된다.
이때 2개짜리 구매는 (2번째 - 3번째)와 1번째의 작은 값으로 구매해 주면 된다.
반대로 2번째 수가 3번째 수보다 작거나 같은 경우에는,
위에서 한 방식 반대로 하면 된다.
먼저 3개짜리를 구매하고, 나중에 1, 2번째 중 작은 값으로 2개짜리를 구매하면 된다.
마지막으로는 남는 arr[i]만큼 1개짜리를 구매하면 된다.
n = int(input())
arr = list(map(int, input().split())) + [0, 0]
answer = 0
for i in range(n):
if arr[i + 1] > arr[i + 2]:
# 첫번째와 두번째를 최대로 구매
count = min(arr[i], arr[i + 1] - arr[i + 2])
answer += count * 5
arr[i] -= count
arr[i + 1] -= count
# 첫번째, 두번째, 세번째를 최대로 구매
count = min(arr[i : i + 3])
answer += count * 7
arr[i] -= count
arr[i + 1] -= count
arr[i + 2] -= count
else:
# 첫번째, 두번째, 세번째를 최대로 구매
count = min(arr[i : i + 3])
answer += count * 7
arr[i] -= count
arr[i + 1] -= count
arr[i + 2] -= count
# 첫번째와 두번째를 최대로 구매
count = min(arr[i], arr[i + 1])
answer += count * 5
arr[i] -= count
arr[i + 1] -= count
answer += arr[i] * 3
print(answer)오늘은 어떤 문제를 풀어볼까 고민하다가, 다이아 5 문제로 들어가 봤다.
이것저것 살펴보다가 다이아 문제 치고는 쉽다고 느껴져서 한번 풀어봤다.
하지만 쉽게 풀릴 거라 생각했지만, 정답을 맞히기까지 생각보다 많이 틀렸다.
차근차근 조건을 보면서 문제를 수정하니 그래도 정답이 나왔다.
처음으로 해결한 다이아 문제라서 굉장히 뿌듯하다.