[python/백준] 18185번: 라면사기 (small)

https://www.acmicpc.net/problem/18185

18185번: 라면 사기 (Small)

 

 

⭐ 문제

 

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다.

 

첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N가 주어진다.

두번째 줄에 N개의 정수 A1, ···, AN가 사이에 공백을 두고 주어진다.

 

 

 

⭐ 코드 분석

 

그리디 알고리즘

 

묶음으로 사지 않으면 갯수당 ３원에 사야하므로 최대한 ３원으로 사야하는 횟수를 줄이고 ３개씩 묶어서 사도록 해야한다。 

만약 [1,2,1,1] 과 같이 주어졌다고 하자. 당연히 3개씩 묶어서 사는게 이득이므로 1번째와 2번째, 3번째에 있는 라면을 구매했다면

[0,1,0,1]이 되어 남은 두개의 라면은 따로따로 구매해야할 것이다. (총 비용 = 7 + 3 + 3 = 13)

만약 3개씩 사지 않고 첫번째와 두번째 라면만 구매한다면 [0,1,1,1]이 되고 깔끔하게 3개씩 구매할 수 있다. (총 비용 = 5 + 7 = 12)

 

즉, arr[i+1] 이 arr[i+2] 보다 큰 경우, 나중에 하나씩 사게 되는 경우를 막기 위해서 arr[i+1] - arr[i+2] 만큼 두 묶음씩 사게 하며

arr[i+1] 과 arr[i+2]이 같아질 때 세 개의 묶음으로 사는 것이 최적해

 

 

 

 

 

⭐ 코드

 

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nums.append(0)

tot = 0

a, b, c = 0, 0, 0

for num in nums:
    a, b, c = b, c, num
    tot += 3 * num
    r = min(a, max(0, b-c))

    tot -= r

    a -= r

    b = min(b, c)

    a = min(a, b)

    tot -= 2 * a

    b -= a

    c -= a

print(tot)

 

 

참고 사이트

 

https://oh2279.tistory.com/133

[백준/파이썬] 18185번 라면 사기(small)