BAEKJOON : 9095, 11052

No. 9095

1. Problem

2. My Solution

• n 의 경우의 수를 구하기 위해 n 보다 작은 (이전의) 값의 결과를 이용 (최적부분구조)
• n 은 3가지의 경우로 나뉠 수 있음
  - n -1 에서 +1 인 경우 n-1 의 모든 경우에 + 1
  - n -2 에서 +2 인 경우 n-2 의 모든 경우에 + 2
  - n -3 에서 +3 인 경우 n-3 의 모든 경우에 + 3

import sys

def solution(n):
    
    if n in dp:
        return dp[n]
    else:
        dp[n] = solution(n-1) + solution(n-2) + solution(n-3)
        return dp[n]

test_n = int(sys.stdin.readline().rstrip())

dp = {}
dp[1] = 1
dp[2] = 2
dp[3] = 4

for _ in range(test_n):
    n = int(sys.stdin.readline().rstrip())
    print(solution(n))

---

No. 11052

1. Problem

2. My Solution

• Top-Down 방식
• 카드 n개 일 때, n개의 카드팩 하나, n-1 의 결과에 1개의 카드팩, n-2 의 결과에 카드팩에 2개의 카드팩 .... 중에 가장 큰 값
• 리스트에 모두 append 한 뒤에 한 번에 비교하고 대입

import sys

def solution(n):
    temp = []
    if dp[n] >= 0:
        return dp[n]
    elif n == 1:
        dp[n] = card[n]
        return dp[n]
    else:
        for i in range(1,n+1):
            temp.append(solution(n-i) + card[i])
    
        dp[n] = max(temp)
        return dp[n]

n = int(sys.stdin.readline().rstrip())
card = [0] + list(map(int,sys.stdin.readline().rstrip().split()))

dp = [0] + [-1] * 1000
print(solution(n))

3. Others' Solution

• Bottom-Up 방식
• dp[i] 를 비교 및 대입하면서 max 설정

import sys

def solution(n):
    for i in range(1,n+1):
        for j in range(1,i+1):
            dp[i]= max(dp[i], dp[i-j] + card[j])

n = int(sys.stdin.readline().rstrip())
card = [0] + list(map(int,sys.stdin.readline().rstrip().split()))
dp = [0] + [0] * 1000

solution(n)
print(dp[n])

4. Learned

• Top-Down 방식과 Bottom-Up 방식 중에서 좀 더 적절한 방법을 사용하자
• 점화식을 최대한 구현해보자