11052. [Python]카드 구매하기

1. 문제

 

https://www.acmicpc.net/problem/11052

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• DP(다이나믹 프로그래밍)

 

3. 파이썬 코드

 

# i 장을 구매하기 위한 최대값 계산 방법 접근

N = int(input())
# 카드 리스트 저장
card_list = list(map(int,input().split()))
# dp 시작
dp = [0] * (N+1)
# dp[1] 값 card_list[0] 으로 초기화
dp[1] = card_list[0]
# N+1 까지 반복문
for i in range(2,N+1):
    # i 값까지 반복문 시행
    for j in range(1,i+1):
        # i 번 dp 에는 i 번째 카드를 구매하기 위해서 최대 값을 갱신해야함
        # i-j 의 경우 dp[i]의 카드를 구매하기 위해 최대값이 들어가있으므로 그 값 + card_list[j-1] 인덱스 값을 더해주면 dp[i] 에 저장된 값과 max 값을 비교하여 갱신해줌
        dp[i] = max(dp[i-j] + card_list[j-1], dp[i])

print(dp[-1])

 

4. 문제를 풀고난 후 생각

 

• 카드를 구매하기 위해서 i 번째 인덱스에 i 번째 카드를 구매하기 위한 최대값을 저장하는 방식으로 접근함.
• 1개 카드를 구매하기 위해서 1번에 들어갈 수 있는 max 값을 넣어둔 후 2개 카드를 구매하기 위해 들어갈 수 있는 최대값을 1개에서 구해 둔 값에서 2-1 인덱스 카드 값을 더해서 기존의 i 에 있는 값과 비교해 max 값을 갱신해 가는 구조이다.

• 위 그림처럼 계속해서 장수가 쌓일수록 이전의 최대값을 가져와서 card[index] 를 더해가며 값을 갱신해준다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(다이나믹 프로그래밍)