문제 : https://www.acmicpc.net/problem/11052

문제 요약

주어진 수 N개의 카드팩을 가장 비싸게 사는 방법을 찾아 출력하는 문제이다.

접근

• DFS를 이용할 경우 시간초과가 발생한다. N의 최대값이 1,000이라 재귀 깊이 역시 최대 1,000이기 때문이다.
• 기본적으로 다이나믹 프로그래밍을 이용하여 접근해야한다.

다이나믹 프로그래밍

다음과 같은 입력이 주어졌을 때 4 3 5 15 16

1. 카드팩의 가격을 다음과 같이 리스트에 저장했다고 하자. a = [0, 3, 5, 15, 16] - 혼동을 방지하기 위해 0번 인덱스를 추가했다.

2. 카드팩을 단 1장만 사려고 한다면? 경우의 수는 가격이 a[1]인 1장짜리 카드팩을 사는 경우밖에 없다. 이를 dy[1] = 3이라 하자. 여기서 dy[i]는 i장을 구입하려 할 때 가격의 최대값이다.

3. 카드팩을 2장까지 사려고 한다면? 경우의 수는 i. 가격이 a[2]인 카드팩을 하나 사는 경우 ii. 가격이 a[1]인 카드팩을 2개 사는 경우 2가지 이다.

여기서 ii의 경우, 우리는 이미 dy[1]을 알고 있으므로, 여기에 1장짜리 카드팩의 가격을 더해 주면 된다. 이를 dy[1] + a[1]로 나타낼 수 있다.

1. 카드팩을 3장까지 사려고 한다면?
   • i. 가격이 a[3]인 카드팩을 하나 사는 경우 dy[0] + a[3]
   • ii. 1장 구입할 때의 최대값 + 1장짜리 카드팩 가격 dy[1] + a[2]
   • iii. 2장 구입할 때의 최대값 + 2장짜리 카드팩 가격 dy[2] + a[1]

위 3가지 경우의 최대값이 dy[3]이 된다.

1. 마지막으로 카드팩 4장을 사려고 한다면
   • i. dy[0] + a[4]
   • ii. dy[1] + a[3]
   • iii. dy[2] + a[2]
   • iv. dy[3] + a[1]

위 4가지 경우의 최대값이 dy[4]가 된다.

결론은 구하려고 하는 N까지 모든 경우의 수에 대해 for문을 돌아 dy[N]까지 구한 뒤, dy[N]을 출력하면 된다.

코드

import sys
input = sys.stdin.readline

if __name__=="__main__":
    N = int(input())
    lst = list(map(int,input().split()))
    lst.insert(0,0) # 인덱스 혼동 방지를 위해 dy[0] = 0 추가
    dy = [0] * (N+1) # 최대 가격을 저장할 배열 생성
    dy[1] = lst[1]
    for i in range(2,N+1):
        max_num = 0
        for j in reversed(range(i)): # 모든 경우의 수에 대해 반복문을 돈다.
            temp = dy[j] + lst[i-j]
            if temp > max_num: # dy[i]에는 최대값을 저장해야 하므로, if문 이용
                max_num = temp
        dy[i] = max_num
    print(dy[N])