[백준/BOJ] 11052번 카드 구매하기 (Python)

[백준/BOJ] 11052번 카드 구매하기

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

문제를 처음 읽고, 처음에는 백트래킹 문제인 줄 알았다. n을 만드는 수의 조합을 찾아야하나 싶었는데, 분류를 보니 dp여서 dp방식으로 풀어야한다는걸 알았다.

1개 부터 n개 까지 카드팩을 구매하는 최댓값을 구하면서 값을 올리면 되겠다고 생각했고, dp방식으로 접근하니 금방 알 수 있었다. dp가 조금씩 익숙해지는 것 같다.

 

알고리즘

1. n과 p를 입력받고, dp를 n+1의 크기로 만들어준다

2. i는 1부터 n+1까지, j는 1부터 i+1까지 이중으로 반복문을 돌면서 dp[i]의 값과 dp[i-j]+dp[j]의 값 중 큰 값을 dp[i]에 넣어준다.

3. dp[n]을 출력한다.

 

Python code

n=int(input())
p=[0]+list(map(int, input().split()))

dp=[0]*(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])