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

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

18185번: 라면 사기 (Small)

티어에 비해 쉽게 풀렸던 문제이다.

이 문제의 핵심 알고리즘은 "갯수 당 가격"이 가장 큰 3원을 사용하는 연산의 횟수를 최소화하고, 그 경우 중에서도 5원을 사용하는 횟수를 최소화하는 것과 arr[i+1]번째 값과 arr[i+2]번째 값의 비교이다!

 

-> 만약 [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]이 같아질 때 세 개의 묶음으로 사는 것이 Greedy 하다!

 

-> 문제 풀이의 기준은 arr[i]번째 값이다! 만약 [1,0,1]처럼 5원이나 7원을 이용한 연산이 불가능한 경우 또는 [3,1,0]처럼 5원 연산을 적용해도 arr[i]에 값이 남아있는 경우를 대비해 항상 정답에 arr[i]*3을 해준다!

 

그리고 그냥 Index overflow를 막기 위해서 메모리를 좀 많이 사용했다.. 분명 더 좋은 알고리즘이 있을 것이라 생각한다.

(굳이 10만이 아니더라도 10002정도면 충분하다. 최대값 10000에 +2만큼 더 탐색하니까..)

 

import sys
input = sys.stdin.readline

n = int(input())
ans,cnt=0,0
arr = [0 for _ in range(100000)]

buf = list(map(int, input().split()))

for i in range(len(buf)):
    arr[i] = buf[i]
    
for i in range(n):
    
    if arr[i+1]>arr[i+2]:
        # 첫번째와 두번째에서 라면을 먼저 최대한으로 산 뒤
        cnt = min(arr[i], arr[i+1]-arr[i+2])
        ans += 5*cnt
        arr[i]-=cnt; arr[i+1]-=cnt

        # 첫번째 두번째 세번째 라면을 최대한으로 구매
        cnt2 = min(arr[i], min(arr[i+1], arr[i+2]))
        ans+=7*cnt2
        arr[i]-=cnt2; arr[i+1]-=cnt2; arr[i+2]-=cnt2;
    
    # 세번째 값이 두번째 보다 더 클 때는 반대로
    else: 
        cnt2 = min(arr[i], min(arr[i+1], arr[i+2]))
        ans+=7*cnt2
        arr[i]-=cnt2; arr[i+1]-=cnt2; arr[i+2]-=cnt2;
        
        cnt = min(arr[i], arr[i+1])
        ans += 5*cnt
        arr[i]-=cnt; arr[i+1]-=cnt
       
    ans += 3*arr[i];
print(ans)