[백준 18185] 라면 사기 (Small)

문제 출처 : https://www.acmicpc.net/problem/18185

문제 이해하기

라면을 최대한 싸게 사면 되는 문제 입니다. 1개를 살 때에는 3원, 2개를 살 때에는 5원, 3개를 살 때에는 7원을 주고 사야 합니다. 최대한 많이 사는 것이 이득이기 때문에 그리디로 문제를 해결할 수 있습니다.

하지만 그리디 문제는 반례를 찾기가 힘듭니다. 반례를 잘 찾아 문제를 해결해야 합니다. 반례는 3개를 살펴볼 때 나오는 것이 아니라 4개 이상일 때 발생 합니다.

 

라면이 위와 같이 있다고 하겠습니다. 그리디 알고리즘으로 한꺼번에 많이 사는것이 이득이기 때문에 처음에 3개를 사보겠습니다.

3개를 한꺼번에 샀기 때문에 3 * 7 로 21의 돈이 들었습니다. 그리고 2번째 2개, 4번째 3개가 남았습니다. 각각의 3원으로 사면 21 + 2 * 3 + 3 * 3 = 36의 돈이 듭니다.

하지만 4번째 라면을 고려해서 다음에 연속해서 살 수 있는 부분을 고려해서 문제를 해결해 보겠습니다. 뒤에 또다시 3개가 나올지 모르기 때문에 2개만 먼저 사는 것입니다.

앞에서 2개를 먼저 샀기 때문에 5 * 2 = 10의 돈이 들었습니다. 그리고 나머지 앞의 1개를 구매합니다.

지금까지 10 + 3으로 13이 들었습니다. 그리고 마지막으로 2번째부터 4번째까지 3개를 동시에 구매합니다. 그럼 13 + 3 * 7 = 13 + 21 = 34가 됩니다. 아까 앞에서부터 무작성 살 때보다 2원 이득을 보았습니다. 따라서 이런 부분을 고려하여 문제를 해결해야 합니다.

코드 작성

앞 서 나온 문제를 해결하면서 코드를 작성해 보겠습니다.

입력 받기

N = int(input())

arr = list(map(int, input().split())) + [0, 0]
ans = 0
price = [0, 3, 5, 7]

라면 공장의 개수 N을 입력 받습니다. 다음으로 공장마다 라면을 사야하는 개수를 arr이라는 리스트에 담았습니다. arr의 마지막에는 [0, 0]을 추가하였습니다. 이는 총 3개의 공장 라면 개수를 확인해야 하기 때문에 리스트의 범위를 벗어나지 않게 하기 위해서 2개의 0을 추가로 넣은 것입니다.

ans는 우리가 지불해야할 총 돈의 금액을 0원으로 초기화 한 것입니다. 마지막으로 price는 1개를 살 때는 3원, 2개를 살 때에는 5원, 3개를 살 때에는 7원이 든다는 것을 리스트로 표현하였습니다.

라면 구매하기

for i in range(N):
    if arr[i + 2] < arr[i + 1]:
        k = min(arr[i], arr[i + 1] - arr[i + 2])
        buy(2, i, k)
        buy(3, i)
    else:
        buy(3, i)
        buy(2, i)
    
    buy(1, i)

print(ans)

처음부터 전체 공장을 돌면서 라면을 구매하는 로직 입니다. 기본적으로 3개를 살 수 있으면 사고, 다음 2개를 살 수 있으면 사고, 마지막으로 1개를 살 수 있으면 사는 것입니다. else 다음을 보면 3개, 2개, 1개 순으로 buy 함수를 사용하여 사는 것을 볼 수 있습니다.

하지만 위에서 반례를 보였듯이 그냥 3개, 2개, 1개를 사면 안됩니다. 4번째에 있는 항목으로 다음번에 3개를 연속해서 살 수 있다면 그렇게 해주어야 합니다. 그래서 3번째 항목보다 2번째 항목이 더 크다면 2개를 먼저 사고, 다음에 3개를 사도록 바꿔준 것입니다. 그 부분이 if문 부분 입니다.

buy 함수

def buy(n, idx, k = 0):
    global ans

    if k == 0:
        k = arr[idx]
        for i in range(1, n):
            k = min(k, arr[idx + i])

    for i in range(n):
        arr[idx + i] -= k

    ans += price[n] * k

buy 함수에는 3개의 매개변수가 들어갑니다. 먼저 n은 1개를 살지, 2개를 살지, 3개를 살지를 정하는 인자 입니다. idx는 리스트의 몇번째 인덱스를 기준으로 삼을지 정하는 인자입니다. 마지막으로 k값은 한꺼번에 몇개를 살지 정하는 인자입니다. k 값은 기본적으로 0이 초기값 입니다. 즉 입력이 되지 않았으면 n개까지 최소 개수를 확인하여 알아서 구매를 합니다. 하지만 k값이 있으면 주어진 개수만큼 구매를 합니다. 이것은 라면을 구매할 때 2번째부터 4번째 연속으로 구매할 여지를 주기 위해 앞에 2개만 구매할 때 사용 합니다.

n의 개수만큼 반복을 하면서 최소값을 구하고 k에 넣습니다. 그 후 k개 구매를 하도록 합니다. 구매한 금액은 ans에 추가하여 최종적으로 출력될 수 있도록 합니다.

전체 코드

전체 코드를 확인하겠습니다.

N = int(input())

arr = list(map(int, input().split())) + [0, 0]
ans = 0
price = [0, 3, 5, 7]

def buy(n, idx, k = 0):
    global ans

    if k == 0:
        k = arr[idx]
        for i in range(1, n):
            k = min(k, arr[idx + i])

    for i in range(n):
        arr[idx + i] -= k

    ans += price[n] * k

for i in range(N):
    if arr[i + 2] < arr[i + 1]:
        k = min(arr[i], arr[i + 1] - arr[i + 2])
        buy(2, i, k)
        buy(3, i)
    else:
        buy(3, i)
        buy(2, i)
    
    buy(1, i)

print(ans)