[BOJ] 1932번: 정수 삼각형(Java)

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

1932번: 정수 삼각형

 

문제

 

입력

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

 

출력

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

 

난이도

실버 1

 

Sol

역으로 삼각형의 맨 아래쪽부터 위로 한 칸씩 올라가면서 인접한 값 중 최댓값을 찾아 누적한다. 맨 아래 층부터 꼭대기까지 누적을 반복하고, 최종적으로 누적값(triangle[0][0])을 출력한다.

public class B1932_정수삼각형 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(token.nextToken());
        int[][] triangle = new int[n][n+1];

        for(int i=0; i<n; i++){
            token = new StringTokenizer(bf.readLine());

            for(int j=0; j<i+1; j++){
                triangle[i][j] = Integer.parseInt(token.nextToken());
            }
        }
        // input

        for(int i=n-1; i>0; i--){
            for(int j=0; j<i; j++){
                triangle[i-1][j] += Math.max(triangle[i][j], triangle[i][j+1]);
            }
        }
        // operation

        System.out.println(triangle[0][0]);
        // output
    }
}

 

😅

• triangle 배열과 dp 배열을 따로 생성했다가 시간 단축을 위해 triangle 배열 하나에서 연산을 끝냈다
• ArrayList를 사용하고 싶었는데 반복문을 어떻게 돌려야 할지 헷갈려서 사용하지 못했다..