Algorithm, boj, 카드 구매하기(11052)
풀이
- 4장을 사고싶다면
- bottomup방법을 사용했다.
- 1장을 살수 있는 최대값 dp[1]
- 2장을 살수 있는 최대값
dp[2] = Math.max(dp[2], card[1]+dp[1]); dp[2] = Math.max(dp[2], card[2]+dp[0]); // card[1]+card[1] or card[2] 중에 큰값을 고른다 - 3장을 살수 있는 최대값 ```java dp[3] = Math.max(dp[3], card[1]+dp[2]); dp[3] = Math.max(dp[3], card[2]+dp[1]); dp[3] = Math.max(dp[3], card[3]+dp[0]);
// 카드1장짜리 + 카드2장을 살수있는 최대값 // 카드2장짜리 + 카드1장을 살수있는 최대값 // 카드3장짜리
```java
package org.baekjoon;
import java.util.Scanner;
public class test11052_dp_buyCard {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] card = new int[num+1];
int[] dp = new int[num+1];
for (int i=1; i<=num; i++)
card[i] = sc.nextInt();
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= i; j++) {
dp[i] = Math.max(dp[i], card[j] + dp[i - j]);
}
}
System.out.println(dp[num]);
}
}