자바(백준) 1932 정수 삼각형

오답 노트 & 새로 알게 된 점

DP를 세 문제를 풀어보니 어떻게 푸는지 감이 오는 것 같다. 항상 문제를 풀 때, 3~4번째까지는 규칙성을 찾기 위해, 나열하는 것이 중요하다. 이 문제를 예로 들면,

7
10 = 7 + 3 count[1][0] = triangle[0][0] +                    triangle[1][0]	15 = 7 + 8 count[1][1] = triangle[0][0] +                    triangle[1][1]
18 = 7 + 3 + 8 count[2][0] = count[1][0] +                    triangle[2][0]	11 = 7 + 3 + 1, 16 = 7 + 8 + 1 count[2][1] = Math.max(count[1][0] +                    triangle[2][1],                    count[1][1] +                    triangle[2][1])	15 = 7 + 8 + 0 count[2][2] = count[1][1] +                    triangle[2][2]

이런 식으로 나타난다. 

규칙성을 보면, 제일 왼쪽, 열이 0일 때는 count[i][j] = count[i-1][j] + triangle[i][j] 규칙성을 보인다.

 

가운데는 양쪽에서 값을 받기 때문에, 그 중 큰 값을 받으면 된다. 그래서

count[i][j] = Math.max(count[i-1][j-1] + triangle[i][j], count[i-1][j] + triangle[i][j]) 을 만족한다.

 

제일 오른쪽, 열과 행이 같을 때(i == j), count[i][j] = count[i-1][j-1] + triangle[i][j]을 만족한다.

 

코드

package Dynamic_Programming;
 
import java.io.*;
import java.util.*;
 
class Main{
    static int size;
    public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine());
 
         size = Integer.parseInt(st.nextToken());
 
         int triangle[][] = new int[size][size];
         int count[][] = new int[size][size];
 
         for(int i = 0; i < size; i++){
             st = new StringTokenizer(br.readLine());
             for(int j = 0; j < i+1; j++){
                 triangle[i][j] = Integer.parseInt(st.nextToken());
             }
         }
 
         count[0][0] = triangle[0][0];
         int max = Integer.MIN_VALUE;
         for(int i = 1; i < size; i++){
             for(int j = 0; j <= i; j++){
                 if(j == 0) count[i][j] = count[i-1][j] + triangle[i][j];
                 else if(i == j) count[i][j] = count[i-1][j-1] + triangle[i][j];
                 else{
                     count[i][j] = Math.max(count[i-1][j-1] + triangle[i][j], count[i-1][j] + triangle[i][j]);
                 }
                 max = Math.max(max, count[i][j]);
             }
         }
         System.out.print(max);
    }
}