카드 구매하기
접근 방법 : DP 다이나믹 프로그래밍
DP란 하나의 큰 문제를 여러개의 작은 문제로 저장하여 그 결과를 저장하여 다시 재사용 하면서 큰 문제를 해결하는 방식이다.
예시 DP[i] = DP[i-1] + DP[i-2] 이런식의 피보나치 등
카드 구매하기 문제를 DP에 적용시켜보자.
P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다.
그래? 이게 무슨 말일까? 4장의 카드를 살 것인데 우리의 주인공은 카드 1장의 가격이 비싸면 가치가 있다고 생각하는구나! 4장이 가장 큰 가질려면 p2*2 인 10원이 필요하구나
보통의 사람이라면 다음과 같이 접근한다.
p1 의 가치 1/1 = 1
p2 의 가치 5/2 = 2.5
p3 의 가치 6/3 = 2
p4 의 가치 7/4 = 1.75
오 p2 4장이면 되겠네
하지만 컴퓨터한테는 다음과 같이 접근해야 한다.
모든 계산을 할 수 있도록
사야 할 카드는 4장인데
p1을 사는게 가치가 있을까? p1을 사지 않는게 가치가 있을까?
p1을 산다면 사야 할 카드는 3장인데
p1을 또 사는게 좋을까? p1을 안사는게 좋을까?
p1을 안산다면? p2를 사는게 좋을까 안사는게 좋을까?.............
경우의 수가 정말 많다.. 하지만 컴퓨터는 해결해준다.
p1 (o) p1(o) p1 (o) p1(o)
p1 (o) p1(o) p1 (o) p1(x) ------ 이 방법은 실패
p1 (x) p2 (o) p1(o) p1(o)
p1 (x) p2 (o) p1(o) p2 (o)
.
.
.
이 코딩테스트는 수학 문제 풀때처럼 핵심적인 부분이 반복해서 나타난다.
-
전체 dp의 개수 이번 문제에서 n은 최대 1000개가 주어진다. 따라서 dp[1001] 을 선언해주자 1000이 아니고 1001인 이유는 dp[0]은 제외하기 때문이다.
-
dp[i] = dp[i-1]~ 이라는 하나의 식
이번문제에서 특정 카드의 개수를 택하는 최대값은 다음과 같은 식으로 정리된다.
dp[i] = Math.max(dp[i], dp[i-j] + p[i])
dp[i] 란 특정 카드의 개수를 택하는 최대값이다.
dp[i-j] 란 i란 남은 카드의 개수를 의미한다. j란 구매한 카드팩을 의미한다.
즉 구매한 카드팩은 1 이상일 것이고 구매한 카드팩은 전체 카드의 개수를 넘지 못한다.
1 <= j <= i 이가 된다.
이를 for문으로 해결하자면
dp[1] ~ dp[4] 를 구하는 과정에서
dp[1] = dp[1] 을 택하거나 dp[1-1] + p[1] 을 택한다는 것을 의미한다.
dp[1] 은 이고 dp[0]+1 이므로 dp[1] 에는 1이 들어간다.
카드 한장을 고르는 최대 가치는 1이 되는 것이다. 이런식으로
4장을 고르는 최대값을 찾게 된다.
