BOJ 1932: 정수 삼각형 문제 풀이

이번주 2020-07-27의 알고리즘 스터디 문제인

 

BOJ 1932: 정수 삼각형 문제를 풀어보았습니다.

 

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

이 문제는 2차원 DP 문제로서 삼각형 형태로 받은 입력을 토대로

 

층마다 하나의 수를 더해서 맨아래층에 도달했을때 최대값을 찾는 문제입니다.

 

제 문제 풀이 소스는 다음과 같습니다.

 

/* import ... */
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        int max = 0;

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        sc.nextLine();

        if(n < 1 || n > 500) {
            System.out.println("잘못된 범위를 입력하셨습니다. (1<= n <= 500)");
            return;
        }

        int[][] input = new int[n][];
        int[][] dp = new int[n][];

        for (int i = 0; i < n; i++) {
            input[i] = new int[i+1];
            for (int j = 0; j < i+1; j++) {
                input[i][j] = sc.nextInt();
            }
            sc.nextLine();
        }

        dp[0] = new int[1];
        dp[0][0] = input[0][0];

        if(n == 1) {

            System.out.println(dp[0][0]);

        } else {
            int count = 0;

            for (int i = 1; i < n; i++) {
                dp[i] = new int[i*2];
                for (int j = 0; j < i+1; j++) {
                    if(j==0) {
                        dp[i][j] = dp[i-1][j] + input[i][j];
                    } else if(j == i) {
                        dp[i][j] = dp[i-1][j-1] + input[i][j];
                    } else {
                        dp[i][j] = Math.max(dp[i-1][j] + input[i][j], dp[i-1][j-1] + input[i][j]);
                    }

//                    System.out.println(dp[i][j]);

                    if(i == n-1 && max < dp[i][j]) {
                        max = dp[i][j];
                    }
                }
            }
        }

        System.out.println(max);
    }
}

소스코드 : https://github.com/lsjjong8/Algorithm-Study/blob/master/0.%20WSAPT-Study/BOJ1932.java

 

저는 이중 for 문을 썼습니다.

 

Max값으로 비교하여 해결하였습니다.

(dp 배열의 크기는 경우의 수를 다 따져 i층에 i*2 만큼의 배열을 할당하는 방법으로는 실패를 겪음)

 

그리고 맨 아래층에서 max를 비교하여 최대값을 찾아 출력하였습니다.

 

예제 입력과 출력대로 나오는 것을 확인할 수 있었습니다 :)