[백준] 18186 - 라면 사기(Large) (python)

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

18186번: 라면 사기 (Large)

문제

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).

교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.

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

최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N과 두 자연수 B, C가 사이에 공백을 두고 주어진다.

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

출력

첫 번째 줄에 교준이가 필요한 최소 금액을 출력한다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

• 3 ≤ N ≤ 106
• 1 ≤ B ≤ 106
• 1 ≤ C ≤ 106
• 0 ≤ Ai ≤ 106 (1 ≤ i ≤ N)

예제 입력 1

3 2 2
1 0 1

예제 출력 1

4

예제 입력 2

5 3 2
1 1 1 0 2

예제 출력 2

13

풀이

a,c,d=map(int, input().split())
b=list(map(int, input().split()))
b.append(0)
b.append(0)
cnt=0

if min(c,d) == d : 
    for i in range(len(b)-2):
        if b[i+1] > b[i+2] and b[i+2] != 0 :
            m = min(b[i+1]-b[i+2],b[i])
            cnt+=m*(c+d)
            b[i] = b[i] - m
            b[i+1] = b[i+1] - m
        if b[i+2] > 0 and b[i+1] > 0 and b[i] > 0 :
            m = min(b[i],b[i+1],b[i+2])
            cnt+=m*(c+2*d)
            b[i] = b[i] - m
            b[i+1] = b[i+1] - m
            b[i+2] = b[i+2] - m
        if b[i] != 0 and b[i+1] != 0 and b[i+2] == 0 :
            m = min(b[i],b[i+1])
            cnt+=m*(c+d)
            b[i] = b[i] - m
            b[i+1] = b[i+1] - m
        if b[i] != 0 :
            cnt+=b[i]*c
            b[i]=0
else:
    for i in range(len(b)-2):
        if b[i] != 0 :
            cnt+=b[i]*c
            b[i]=0    
        
print(cnt)

문제를 보면, 우선 B와 C의 수에 따라 계산 방식이 달라진다.

 

1개를 구매하는 가격은 B 

2개를 구매하는 가격은 B+C

3개를 구매하는 가격은 B+2C

 

B가 C보다 작다면 라면은 세트로 묶어서 사는것 보단 하나씩 사는게 훨신 저렴하다. 그러므로 마지막의 else를 통해 하나씩 라면을 사는 방법을 구현했고,

만약 B가 C보다 크다면 라면을 세트로 구입해야 하는데 하나만 주의하면 된다.

예를 들어, 3 4 3 1 이라는 입력을 받았을 때, 그리디 알고리즘은 탐욕적 알고리즘이기에 7개 먼저 구입한다면, 0 1 0 1이 남아 21 + 6 즉 27이라는 비용이 지불하는데, 

[I+1]이 [I+2]보다 크다면 5개를 먼저 min([i+1]-[i+2],[i]) 만큼 구입한 후, 7개 만큼 구입해주는 것이 비용적으로 5+14+7 = 26 이라는 결과가 나오게 된다.

이 부분만 주의한다면, 나머지는 조건문에 해당하는 만큼 7을 살 수 있을 경우 7, 5, 3 순으로 진행한다.

 

그리디 알고리즘이란걸 알고 풀었기에 비교적 쉽게 풀 수 있었다.