문제
[ 문제 조건 ]
- 카드 개수 < 가격
- i개의 카드, 가격은 Pi
- 즉, 가격을 최대값으로 구해야 한다.
[ 예제 풀이 ]
#1장 샀을때 최대가격 dp[1] =1
dp[1] = dp[1], dp[0] + list[1]
#2장 샀을때 최대가격 dp[2] = 5
dp[2] = dp[2], dp[1] + list[1] #1 + 1 (1장짜리 2개)
dp[2] = dp[2], dp[0] + list[2] #0 + 5 (2장짜리 1개)
#3장 샀을때 최대가격 dp[3] = 6
dp[3] = dp[3], dp[2] + list[1] #5 + 1 (2장짜리 1개 + 1장짜리 1개)
dp[3] = dp[3], dp[1] + list[2] #1 + 5 (1장짜리 2개 + 2장짜리 1개)
dp[3] = dp[3], dp[0] + list[3] #0 + 6 (3장짜리 1개)
#4장 샀을때 최대가격 dp[4] = 10
dp[4] = dp[4], dp[3] + list[1] #6 + 1 (3장짜리 1개 + 1장짜리 1개)
dp[4] = dp[4], dp[2] + list[2] #5 + 5 (2장짜리 2개) *정답*
dp[4] = dp[4], dp[1] + list[3] #1 + 6 (1장짜리 1개 + 3장짜리 1개)
dp[4] = dp[4], dp[0] + list[4] #7 (4장짜리 1개)
[ 점화식 ]
dp[i] = max (dp[i-j], dp[i-j] + list[j] )
✏️한줄평
다이나믹 프로그래밍 알고리즘의 정석 같은 느낌의 문제다. 점화식을 세우는 건 그래도 헷갈린다. 예제를 풀이하다가도 왜 이게 이 값이였지 헷갈리는게 DP 문제인 듯 하다😅
코드
'알고리즘' 카테고리의 다른 글
[Python] map 함수로 2차원배열의 최대값 구하기 (0) | 2021.08.09 |
---|---|
[Python] 백준 9020번 - 골드바흐의 추측 (0) | 2021.08.06 |
[JAVA] 백준 1245 - 농장 관리 (0) | 2021.07.26 |
[JAVA] 백준 11057 - 오르막 수 (0) | 2021.07.25 |
[JAVA] 백준 7569번 - 토마토 (0) | 2021.07.25 |