똥그래미 코딩공장
백준 11052번(카드 구매하기) 파이썬 본문
https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
이 문제는 DP 문제이다.
점화식만 구하면 쉽게 풀 수 있는 문제이다.
그러나...
점화식 구하는게 쉽지가 않다...
점화식을 못구하겠어서 결국 챗 GPT한테 물어봤는데 친절하게 설명해줬다;;
DP는 진짜 점화식 구하는게 관건이다.
n = int(input())
price = list(map(int,input().split()))
dp = [0]*(n+1)
for i in range(1,n+1):
tmp = []
for j in range(1,i+1):
dp[i] = price[j-1]+dp[i-j] # 점화식!!
tmp.append(dp[i])
dp[i]=max(tmp)
print(dp[n])'Algorithm' 카테고리의 다른 글
| 백준 13549번(숨바꼭질 3) 파이썬 (0) | 2023.02.22 |
|---|---|
| 백준 2230번(수 고르기) 파이썬 (0) | 2023.02.21 |
| 백준 6603번(로또) 파이썬 (0) | 2023.02.17 |
| 백준 11403번(경로찾기) 파이썬 (0) | 2023.02.12 |
| 백준 1149번(RGB거리) 파이썬 (0) | 2023.02.10 |