boj)16194 - 카드 구매하기 2
2020. 9. 17. 13:02ㆍPS/boj
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
// # 카드 구매하기 2
public class boj_16194 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception {
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] p = new int[n+1];
int[] dp = new int[n+1];
for (int i = 1; i <= n; i++) {
p[i] = Integer.parseInt(st.nextToken());
}
Arrays.fill(dp, 1000 * 10000);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i-j] + p[j]);
}
}
System.out.println(dp[n]);
}
}
- N개의 카드를 구매할때 마지막 카드팩에 올 수 있는 카드의 수는 1 ~ N 개
- 초기값을 1000 * 10000 으로 채워줌 , n의 최댓값 1000, p의 최댓값 10000
- 최솟값이니 min으로 비교
'PS > boj' 카테고리의 다른 글
boj)10844 - 쉬운 계단 수 (0) | 2020.09.17 |
---|---|
boj)15590 - 1, 2, 3 더하기 5 (0) | 2020.09.17 |
boj)11052 - 카드 구매하기 (0) | 2020.09.17 |
boj)9095 - 1, 2, 3 더하기 (0) | 2020.09.16 |
boj)11727 - 2xn 타일링 2 (0) | 2020.09.16 |