https://www.acmicpc.net/problem/1932!
문제
실버 1 정도의 dp 문제이다.
사실 난이도에 비해서 좀 쉬워보인다
피라미드 처럼 숫자들이 쌓여있고, 밑에 있는 두수들만 더하기가 가능하다.
최종적으로 제일 밑줄에서 가장 큰 수를 구하는 문제이다
입력이
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
이런 식으로 되므로
dp[n][m] = Math.max(dp[n-1][m], dp[n-1][m-1]);
라는 점화식을 세워볼 수 있다.
풀이
입력을 저장하는 배열, dp 배열을 static으로 선언해줘야 한다.
Base Case를 잘 잡아주는게 중요한데, 2차원 배열에서 모든 행의 인덱스 0같은 경우에는 (array[n][0]) 위의 행에서 더할 수 있는 값이 하나밖에 없으므로 (선택지가 없으므로) 우선적으로 맨 왼쪽의 값들을 Base Case로 설정하고 dp 안의 값을 채워주었다
이후, 계산해놓은 Base Case 값을 이용하여 dp[1][1] 부터 차례대로 계산해주면 된다.
모든 행의 맨 오른쪽 인덱스의 경우도 더할 수 있는 선택지가 하나밖에 없지만, 이렇게 구현하려고 했더니 이유모를 ArrayIndex 에러가 나서 1시간 동안 고생했다.
어차피 맨 오른쪽 인덱스의 위의 값은 0이니, 맨 왼쪽 값만 Base Case로 설정하여 풀어도 지장이 없다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] array, dp;
static int answer, n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
array = new int[n][n];
dp = new int[n][n];
for(int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<i+1; j++){
array[i][j] = Integer.parseInt(st.nextToken());
}
}
dp[0][0] = array[0][0]; // Base Case들 먼저 채우기
for(int i=1; i<n; i++) {
dp[i][0] = dp[i-1][0] + array[i][0]; // 맨왼쪽줄
}
find(1); // 값이 없는 맨 위 값
System.out.print(answer);
}
private static void find(int depth) {
if(depth == n){
int max = 0;
for(int i=0; i<n; i++){
if(max < dp[n-1][i]){
max = dp[n-1][i];
}
}
answer = max;
return;
}
for(int i=1; i<=depth; i++){
dp[depth][i] = Math.max(dp[depth-1][i], dp[depth-1][i-1]) + array[depth][i];
}
find(depth+1);
}
}
느낀 점
실버 1문제 치고는 쉬웠다.
원래는 베이스 케이스를 왼쪽줄 오른쪽줄 두가지로 놓고 풀려고 했는데, ArrayIndex 에러가 한시간 동안 고쳐지지 않아서 한쪽으로만 Base Case를 놓고 풀었다.
왜 두쪽을 다 설정해놓고 풀면 안되는건지 생각해보아야겠다
