[알고리즘] 백준 1932 정수 삼각형 -dp-

 

 

RGB 문제에 이어서 dp 다음 단계 문제를 풀어봤습니다. 둘 다 dp 문제이므로 성향은 비슷합니다.

 

과거의 값을 이용해 최대가 되는 값을 알아내가는 문제입니다.

 

삼각형 특성 상 왼쪽 구석과 오른쪽 구석은 이전 N-1 줄을 더할 때 한가지 경우의 수밖에 없다는 점과 그 외 가운데 값들은 두가지 경우중 큰 값을 더해줘야 한다는 로직이 필요합니다.

 

주석에 설명을 적어놓았습니다. ㅎㅎ

풀이는 다음과 같습니다.

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 삼각형 높이
        int[][] num = new int[n + 1][n + 1]; // [높이][개수]
        //초기화
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                num[i][j] = sc.nextInt();
            }
        }

        //두번째 줄 부터 n 줄까지 더해나감
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (j == 1) { //왼쪽구석
                    num[i][j] += num[i - 1][1];
                } else if (j == i) { //오른쪽 구석
                    num[i][j] += num[i - 1][j - 1];
                } else { //그 외 중간위치들
                    num[i][j] += Math.max(num[i - 1][j], num[i - 1][j - 1]);
                }
            }
        }
        //결과
        int result = num[1][0];
        for (int i = 1; i <= n; i++) {
            result = Math.max(result, num[n][i]);
        }
        System.out.println(result);
    }
}

 

댓글과 공감은 큰 힘이됩니다. 감사합니다.!!