[BOJ] 11052번 카드 구매하기 / 사용언어 : 파이썬(python)

※ 문제링크 

11052번: 카드 구매하기

해당문제는 동적프로그래밍과 관련된 문제로, 해결을 위해서는 점화식을 도출하는 것이 필수적이었다. 점화식을 도출하기 위해 가장 작은 단위부터 원리를 생각해봤을때, 카드팩을 1개살때는 P1을, 2개살때는 P1 + P1 과 P2중에 큰 값을, 3개 살때는 P1+P1+P1, P2 + P1, P3중 큰 값을 구하면 되었다. 즉, 구해야하는 카드의 수가 i일때, 1부터 i-1까지의 조합들의 값을 반복문을 통해 dp[i]에 저장된 값과 비교하여 큰 값으로 갱신하게끔 하면 되었다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 리스트에 저장하고, dp로 갱신할 리스트를 만들어준다.

2. 2중 반복문을 통해 구입해야하는 카드의 개수가 i개일때의 최대 가격을 갱신하고, 해당 내용을 N까지 반복해준다.

3. 반복문이 종료되면 dp[N]의 값을 출력한다.

 

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

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.