백준 11052번: 카드 구매하기

문제

문제 바로가기> 백준 11052번: 카드 구매하기

풀이

다이나믹 프로그래밍을 이용해 풀었다.

N = int(input())
card_pack = list(map(int, input().split()))
dp = [card_pack[0], card_pack[0]]
for i in range(2, N+1):
    tmp=0
    for j in range(1, i//2+1):
        tmp = max(tmp, dp[j]+dp[i-j])
    dp.append(max(tmp, card_pack[i-1]))
print(dp[N])

코드 개선

아래와 같이 배열하나만 사용해서 구현할 수도 있다. 배열을 만든 후 한번에 비교하므로 시간도 더 단축시킬 수 있다.

N = int(input())
dp = [0]+list(map(int, input().split()))
for i in range(2, N+1):
        dp[i] = max([dp[i-j]+dp[j] for j in range(i//2+1)])
print(dp[N])