[ 2023-03-19 🤥 TIL ]

백준 11052번

저번에 풀었던 문제와 유사한 문제여서 bfs로 풀었다가 답은 맞았는데 시간초과에 걸려버렸다.

import sys

input = sys.stdin.readline

n = int(input())
n_li = list(map(int, input().split()))
cost = 0
com_cost = 0


def bfs(c, val):
    global n, cost

    if c == n:
        if val > cost:
            cost = val
        return val

    for i in range(1, (n - c)+1):
        com_cost = bfs(i+c, val+n_li[i-1])


for i in range(1, n+1):
    com_cost = 0
    bfs(i, n_li[i-1])
print(cost)

👆 시간초과에 걸리는 bfs코드..ㅠ

dp를 사용하여 해결하면 시간초과에 걸리지 않는다기에 어떻게 풀어야하는지 고민해봤는데.. 생각이 나지 않아 결국 답을 찾아보았습니다.

import sys

input = sys.stdin.readline

n = int(input())
p = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n+1)] #카드값이 최대가 되는 비용을 담는 배열


for i in range(1, n+1):
    for j in range(1, i+1):
        dp[i] = max(dp[i], dp[i-j] + p[j]) 
#이전 카드 갯수까지의 가격 합이 최대가 되는 것을 구한다.
print(dp[n])