BOJ#1932 숫자삼각형

BOJ#1932 숫자삼각형

* 문제

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

* 풀이

▷ dp 정의

dp[i][j] : i층에서 j 를 선택했을 때, 0~i 층의 최대값

▷ dp 점화식

dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j+1])

별로 어렵지 않은 문제였지만 시간초과로 고생을 좀 했습니다.

원인으로는 dp 초기값을 0으로 설정했는데 

코드 64라인에서 dp값을 재활용 할 때, 

원래 삼각형 값이 0인 경우와 dp 초기값 0인 경우를 구분하지 못해서 메모이제이션을 하지 못했기 때문입니다.

dp 초기값을 -1으로 고쳐서 해결하였습니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231932_TheTriangle/src

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * BOJ#1932 숫자삼각형
 * https://www.acmicpc.net/problem/1932
 */

public class Main {

    public static void main(String[] args) throws IOException {

        int n;
        int[][] triangle;
        int[][] dp;

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        triangle = new int[n][n + (n - 1)];
        dp = new int[n][n + (n - 1)];

        for (int i = 0; i < n; i++) {

            Arrays.fill(triangle[i], 0);
            Arrays.fill(dp[i], -1);
        }

        int center = n - 1;
        for (int i = 0; i < n; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < (i + 1) * 2; j += 2) {

                triangle[i][center - i + j] = Integer.parseInt(st.nextToken());
            }
        }

        // solve
        int tempMax = 0;
        for (int i = 0; i < 2 * n - 1; i += 2) {

            int cost = solve(triangle, dp, n - 1, i);
            tempMax = tempMax < cost ? cost : tempMax;
        }

        System.out.println(tempMax);
    }

    // dp[i][j] : i층에서 j를 선택했을 때, 0~i층까지의 최대합
    // solve() : dp[i][j]를 구함
    static int solve(int[][] triangle, int[][] dp, int depth, int num) {

        if (num < 0 || num >= triangle[0].length || depth < 0) {

            return 0;
        }

        if (dp[depth][num] != -1) {

            return dp[depth][num];
        }

        return dp[depth][num] = triangle[depth][num] + Math.max(solve(triangle, dp, depth - 1, num - 1), solve(triangle, dp, depth - 1, num + 1));
    }

}