Level
silver 1
Key Point
DP 문제라는 것을 눈치채야한다.
나는 1~N으로 N을 만들 수 있는 모든 경우의 수를 구한다는 점에서 조합과 DP를 떠올렸다.
조합의 경우에는 시간 복잡도가 2^1,000이므로 당연히 불가능하기 때문에 DP를 선택했다. 최대값을 구하라는 부분에서 DP 유형이라는 확신이 들었다.
아, 경우의 수랑 DP가 무슨 상관인가 싶은 사람도 있을텐데 백준의 >>동전1<< 을 풀어보는 걸 추천한다.
Idea
"경우의 수"를 생각해야한다는 점에서 동전 1과 유사하게 풀어보려고 했다.
dp 배열 값을 경우의 수로 설정하고 dp값에 arr값을 곱하여 최댓값을 구할 예정이었다.
아래와 같이 말이다.
시간복잡도와 공간복잡도도 초과하지 않아서 나름 좋은 풀이라고 생각하고 뿌듯해했다.....
1로 1개, 2개, 3개, 4개를 만드는 경우의 수 = 1
2로 1을 만드는 경우의 수 = 0
2로 2를 만드는 경우의 수 = 1
2로 3을 만드는 경우의 수 = 1 (2로 2를 만드는 경우의 수 + 1로 1을 만드는 경우의 수)
....
| 1 | 2 | 3 | 4 | |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 2 |
| 3 | 0 | 0 | 1 | 1 |
| 4 | 0 | 0 | 0 | 1 |
그러나 구현이 생각보다 오래 걸렸고 손코딩해보는 과정에서 문제 난이도에 비해 너무 꼬아서 생각하고 있다는 느낌을 받았다. 정해둔 구현 시간이 넘어가 결국 다른 사람들의 풀이를 보게 되었고 난 아직 멀었다는 걸 깨달았다 ㅎㅎ
불필요하게 최대값을 구하는 식을 따로 세울 필요가 없었다. 애초에 dp를 가격의 최대값으로 설정하면 된다.
그리고 경우의 수도 이중포문으로 해결할 수 있다.
코드만 봤을 땐 파악이 잘 안돼서 예제를 많이 봤다.
예를 들어 4장의 카드를 구매한다고 하자.
4장 =
3장을 구매하는 최대값 + 1장 구매
2장을 구매하는 최대값 + 2장 구매
1장을 구매하는 최대값 + 3장 구매
0장을 구매하는 최대값 + 4장 구매
여기서 4장을 구매하는 최대값 + 0장 구매는 왜 안될까? dp[4]+arr[0]은 어차피 dp[4]와 같기 때문에 의미가 없다.
위의 식을 코드로 옮겨보면 다음과 같다
for(int i=1; i<N+1; i++) {
for(int j=1; j<=i; j++) {
System.out.println(i-j+" "+j);
}
System.out.println();
}
이제 이걸 그대로 arr, dp를 이용하여 옮겨주면 끝이다.
for(int i=1; i<N+1; i++) {
for(int j=1; j<=i; j++) {
// System.out.println(i-j+" "+j);
dp[i]=Math.max(dp[i], dp[i-j]+arr[j]);
}
// System.out.println();
}
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, input;
static int[] arr;
static int[] dp;
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(br.readLine());
arr=new int[N+1];
dp=new int[N+1];
StringTokenizer st=new StringTokenizer(br.readLine());
for(int i=1; i<N+1; i++) {
arr[i]=Integer.parseInt(st.nextToken());
}
// dp
for(int i=1; i<N+1; i++) {
for(int j=1; j<=i; j++) {
dp[i]=Math.max(dp[i], dp[i-j]+arr[j]);
}
}
System.out.println(dp[N]);
}
}