BOJ 다이나믹 프로그래밍 2

🪄 가장 큰 증가 부분 수열

어떤 수열이 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 문제
크기 N (1 ~ 1000)
수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}

n = int(input())
A = [*map(int, input().split())]
dp = A[:]

for i in range(1, n):
    for j in range(i):
        if A[i] > A[j]: dp[i] = max(dp[i], dp[j] + A[i])

print(max(dp))

dp[i]에는 이전 인덱스들 중에서 가장 큰 합과 i 를 더한 값을 넣어주고, 마지막에 dp에서 가장 큰 것을 출력해주면 된다.

🪄 상자넣기

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 문제
크기 N (1 ~ 1000)
상자 B = {1, 5, 2, 3, 7}

n = int(input())
box = [*map(int, input().split())]
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if box[i] > box[j]: dp[i] = max(dp[i], dp[j] + 1)
        
print(max(dp))

이전에 풀었던 가장 긴 증가하는 부분 수열이랑 풀이가 같은 문제이다.

🪄 돌 게임 3

마지막 돌을 가져가는 사람이 게임을 이길 때, 이기는 사람을 구하는 문제
게임 이론은 서로 최선을 다하므로 N의 값에 따라 선공, 후공중에서 누가 이기는지 정해져 있다.

n = int(input())
dp = [0] * (n + 1)
dp[1] = 1; dp[2] = 2; dp[3] = 1; dp[4] = 1

for i in range(5, n+1):
    if dp[i-1] == 2 or dp[i-3] == 2 or dp[i-4] == 2: dp[i] = 1
    else: dp[i] = 2

if dp[n] == 1: print('SK')
else: print('CY')

이전에 풀었던 돌 게임 문제에서 가져갈 수 있는 돌의 개수만 변경되어 있는 문제이다.