[백준] 1932번 - 정수 삼각형 (java)

[Baekjoon 1932 - 정수 삼각형(https://www.acmicpc.net/problem/1932)

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

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

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

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

입력

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

출력

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

풀이

기본적인 DP문제이다.

두가지 방법을 써 보려 한다.

1. 1차원 배열 2개를 이용하는 방법.
2. 차원이 2개인 배열 1개를 이용하는 방법. (토글링)

일단 기본적인 풀이는 같다.

N번째 줄에서 N개의 값을 입력받았을 때

N-1번째 줄의 같은 위치의 값과 이전 위치의 값중 더 큰 값을 선택해 DP 테이블을 업데이트하고

마지막으로 업데이트 된 배열에서 최댓값을 출력하면 된다.

과정

1. 1차원 배열 2개를 이용하는 방법.

1. 배열 DP와 data를 선언하고 현재행의 데이터를 모두 입력받는다.

2. 데이터의 마지막 인덱스부터 1번 인덱스까지 진행한다.

   j번 인덱스에서 dp[j-1]과 dp[j] 중 더 큰 값을 골라 data[j]와 더한 값을 dp[j]에 넣는다.

뒤에서부터 진행하는 이유는 dp가 1차원 배열이기 때문이다.

1번인덱스를 이미 업데이트 시켰다면 2번인덱스가 이미 업데이트 시킨 값을 참조해서 비교하기 때문에

훨씬 큰 값이 나오게 된다.

하지만 뒤에서부터 진행한다면 j-1번 인덱스를 업데이트 시켜야할 때 dp[j]를 참조할 일이 없어서 비교가 가능하다.

import java.io.*;
import java.util.*;

public class BJ_S1_1932 {
    static int N;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        int dp[] = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int data[] = new int[i + 1];
            // 데이터를 입력받아 저장한다.
            for (int j = 1; j <= i; j++) {
                data[j] = Integer.parseInt(st.nextToken());
            }
            // 마지막 인덱스부터 비교하여 값을 저장한다.
            for (int j = i; j > 0; j--) {                
                dp[j] = Math.max(dp[j], dp[j - 1]) + data[j];                
            }
        }
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}

2. 차원이 2개인 배열 1개를 이용하는 방법. (토글링)

마찬가지인 방법이지만 data 배열을 이용하지 않고 값을 입력받으면서 한꺼번에 처리한다.

업데이트 하기 이전 값이 DP[j][0] 에 저장되어 있다면

데이터를 입력받으면서DP[j][0]을 참조하며 DP[j][1]을 업데이트 시키고

다음 행을 업데이트 시킬땐 DP[j][1]을 참조하며 DP[j][0]을 업데이트 시킨다.

모듈러 연산(%)을 이용하여 쉽게 구현할 수 있다.

import java.io.*;
import java.util.*;

public class BJ_S1_1932 {
    static int N;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        int dp[][] = new int[N + 1][2];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <=i ; j++) {
                dp[j][i%2] = Integer.parseInt(st.nextToken()) + Math.max(dp[j-1][(i-1)%2], dp[j][(i-1)%2]);
            }

        }
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dp[i][N%2]);
        }
        System.out.println(ans);
    }
}

결과

시간적인 차이는 그다지 없었다.

490개 가량의 0~ 9999 사이 랜덤값으로 테스트 케이스를 만들어 시간을 측정해 본 결과

방법 1이 방법 2보다 조금 더 빨랐다.

방법 1과 2 모두 O(N^2)이지만 방법 1에서는 포문 안에 포문이 2개이기 때문에 좀 더 느릴 것이라 생각했는데

반대인 결과가 나왔다.

for문 1회 수행하는 것 보다

2차원 배열을 조회하는게 더 느리기 때문이지 않을까 생각한다.