백준: 11052 카드 구매하기

문제

11052번: 카드 구매하기

 

문제 풀이

 이 문제를 효율적으로 풀기 위해서는 메모이제이션(Memoization)을 활용하여야 한다. 문제의 예제와 같이 1 5 6 7이 입력되는 경우 카드 3개 까지 구매할 수 있는 경우의 수는 다음과 같다.

• 카드 1개 구매 : 1개 들어있는 카드 팩
• 카드 2개 구매 : (1개 들어있는 카드 팩) * 2, 2개 들어있는 카드 팩
• 카드 3개 구매 : (1개 들어있는 카드 팩) * 3, 2개 들어 있는 카드 팩 + 1개 들어 있는 카드백, 3개 들어 있는 카드팩
• 즉 카드팩에 든 카드 수의 증가에 따라 경우의 수는 [1], [1 + 1, 2], [1 + 1 + 1, 2 + 1, 3] 이 된다.

 예시에서는 카드 2개를 구매할 경우, 2원 5원 중 5원이 최대 값이므로 5원을 기록한다. 카드 3개를 구매할 경우 1 + 1 + 1은 생각할 필요가 없다. 왜냐하면 1을 선택하는 것은 최대 값이 아니라는 것을 알기 때문이다. 따라서 6원이라는 값을 기록한다. 즉, 카드팩에 수가 작을 때 발생하는 경우의 수에서 최대 값을 찾고, 카드 구매 수 증가에 따라, 이전에 기록해둔 값을 비교하여 지불해야 하는 금액이 가장 큰 값을 찾을 수 있다.

 

코드

if __name__ == '__main__':
    N = int(input())
    card = [0] + list(map(int, input().split()))

    memo = [0] * (N + 1)
    memo[1], memo[2] = card[1], max(card[2], card[1] * 2)

    for i in range(3, N + 1):
        memo[i] = card[i]
        for j in range(1, i // 2 + 1):
            memo[i] = max(memo[i], memo[j] + memo[i - j])
    print(memo[N])