Today's Algorithm(2019-03-18)

baekjoon1932. 정수 삼각형

이전에 프로그래머스에서 풀어봤던 문제인데요. 그때 제가 다른 사람의 풀이를 참고해서 풀었던 것으로 기억해서 다시 한번 풀어보게 되었습니다.

 

이 문제에서 핵심은 '최대값을 어떻게 구할까'인데요. 전에 풀었을 때 재귀로 풀었다가 시간초과가 발생한 기억이 있습니다. 이에 대한 해법은 '다이나믹 프로그래밍'입니다. 쉽게 말하면 그 전까지 값들을 모두 메모해두었다가 다음 계산할 때 사용하는 것입니다. 그럼 어떤 것을 메모할까요?

 

삼각형을 유심히 보면 제일 앞, 제일 뒤를 제외한 그 사이 숫자는 바로 윗줄의 왼쪽 또는 오른쪽에서 오는 수를 받게 됩니다. 이때 최대값을 받기 위해선 둘 중 큰 수를 받아야겠죠. 그것을 착안하면 다음과 같이 구할 수 있을 것입니다.

// d[j - 1] : 삼각형에서 바로 윗줄 왼쪽
// d[j] : 삼각형에서 바로 윗줄 오른쪽
arr[j] += Max.max(d[j - 1], d[j]);

 

처음엔 배열 하나로 재활용할 수 있을까 생각했는데 그렇게 하면 스텝이 좀 꼬일 수 있습니다. 전의 줄의 수를 재활용해야 하는데 그 수가 변화됨으로써 정확한 값을 계산하기 힘든 것이죠. 그렇기 때문에 해당 줄 입력받는 것을 메모하는 배열을 이용하여 변화시킨 다음 다시 메모하는 배열에 반영하는 식으로 계산을 이어나갔습니다.

 

코드는 다음과 같습니다.

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[] d = new int[n];
        d[0] = Integer.parseInt(br.readLine());

        for (int i = 1; i < n; i++) {
            int[] arr = toArray(br.readLine());
            for (int j = 0; j < arr.length; j++) {
                if (j == 0) arr[j] += d[j];
                if (j == arr.length - 1) arr[j] += d[j - 1];

                if (j > 0 && j < arr.length - 1) {
                    arr[j] += Math.max(d[j - 1], d[j]);
                }
            }
            reflect(d, arr);
        }
    }

    private static void reflect(int[] d, int[] arr) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            d[i] = arr[i];
            max = Math.max(max, d[i]);
        }
        if(d.length == arr.length) System.out.println(max);
    }

    private static int[] toArray(String readLine) {
        String[] splitted = readLine.split(" ");
        int[] arr = new int[splitted.length];
        for (int i = 0; i < splitted.length; i++) {
            arr[i] = Integer.parseInt(splitted[i]);
        }
        return arr;
    }
}