2022-10-17 algorithm

boj_1932 정수 삼각형 - silver 1

Link : 정수 삼각형

정보

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력1

예제 출력1

풀이

1. 2차원 배열에 삼각형의 숫자들을 담아준다.
2. 0열인 경우에는 바로 위 오른쪽 숫자만 더할 수 있다.
3. 마지막 열인 경우에는 바로 위 왼쪽 숫자만 더할 수 있다.
4. 중간 부분만 더 큰 숫자를 더하도록 코드를 짜면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < input.length; j++) {
                dp[i][j] = Integer.parseInt(input[j]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (i==0) {    // 0행은 위가 없으므로 건너뛴다.
                continue;
            }
            for (int j = 0; j < i+1; j++) {
                if (j==0) {
                    dp[i][j] += dp[i-1][j];
                } else if (j==i) {
                    dp[i][j] += dp[i-1][j-1];
                } else {
                    dp[i][j] += Math.max(dp[i-1][j-1], dp[i-1][j]);
                }
            }
        }
        int answer = dp[n-1][0];
        for (int i = 1; i < n; i++) {
            if(dp[n-1][i]> answer) {
                answer = dp[n-1][i];
            }
        }
        System.out.println(answer);
    }
}

결과

tags: algorithm, Boj, dfs