-
Notifications
You must be signed in to change notification settings - Fork 0
/
BuyCard.java
104 lines (88 loc) · 2.08 KB
/
BuyCard.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BuyCard {
public static int[] resultArr;
public static int[] dpArr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int number = Integer.parseInt(br.readLine());
String[] arr = br.readLine().split(" ");
initArr(number);
mkResultArr(arr);
System.out.println(getDpResult(number));
}
public static int getDpResult(int number) {
if(number <= 0) return 0;
if(dpArr[number] != -1) return dpArr[number];
int result = Integer.MIN_VALUE;
for(int i = 1; i <= number; i++) {
int value = resultArr[i];
result = Math.max(result, value + getDpResult(number - i));
}
dpArr[number] = result;
return dpArr[number];
}
public static void mkResultArr(String[] arr) {
for(int i = 1; i < resultArr.length; i++) {
resultArr[i] = Integer.parseInt(arr[i-1]);
}
}
public static void initArr(int width) {
resultArr = new int[width + 1];
dpArr = new int[width + 1];
for(int i = 1; i < dpArr.length; i++) {
dpArr[i] = -1;
}
}
}
/**
* 입력
* 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
* 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
*
* 출력
* 첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.
*
* 예제 입력 1
* 4
* 1 5 6 7
*
* 예제 출력 1
* 10
*
* 예제 입력 2
* 5
* 10 9 8 7 6
*
* 예제 출력 2
* 50
*
* 예제 입력 3
* 10
* 1 1 2 3 5 8 13 21 34 55
*
* 예제 출력 3
* 55
*
* 예제 입력 4
* 10
* 5 10 11 12 13 30 35 40 45 47
*
* 예제 출력 4
* 50
*
* 예제 입력 5
* 4
* 5 2 8 10
*
* 예제 출력 5
* 20
*
* 예제 입력 6
* 4
* 3 5 15 16
*
* 예제 출력 6
* 18
*/