Project Euler #81: Path sum: two ways

[congr]

https://www.hackerrank.com/contests/projecteuler/challenges/euler081

Sample Input

5
131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331

Sample Output

2427

[congr]

[0][0] 에서 시작해서 배열 우하단 끝까지 진행하면서 가장 작은 숫자 path 를 찾는 문제다 전에 푼 문제는 가장 큰 패스를 찾는 문제라서 어려움이 없었는데, 작은 패스는 생각치 못한 곳에 문제가 있었다. T[i][j] = A[i][j] + max(A[i-1][j], A[i][j-1]) 일 경우 간단하다. 배열이 모두 자동으로 0으로 초기화 되어 있으므로

min path 찾는 경우 배열을 아주 큰값 혹은 MAX_VALUE로 초기화 안하면 첫번째 라인 i == 0 케이스에서 1 2 3 => 1 3 6 을 기대했다면 바보다. ㅋㅋ

쉬운 문제인 듯 했지만 한시간이상 소요되었다. 디버깅을 하면서도 무엇을 위해 어떤 값을 찾기 위해 디버깅을 하는지 멍한 느낌.... 생각을 구체화하고 노트에 정리하면서 코딩하자..

[congr]

public static void main(String[] args) { // class Solution
    Scanner in = new Scanner(System.in);

    int N = in.nextInt();
    long[][] arr = new long[N + 1][N + 1];

    /* make arr array like below with inputs which has 0 on i == 0 || j == 0
    *  0 0 0 0
    *  0 1 2 3
    *  0 4 5 6
    *  0 7 8 9
    * */
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) arr[i + 1][j + 1] = in.nextInt();
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i - 1][j] == 0) arr[i - 1][j] = Long.MAX_VALUE; // MAX를 구하는 것은 아래 한줄로 되지만 Min을 구하는 것은 초기에 큰값 초기화가 필요하다
            else if (arr[i][j - 1] == 0) arr[i][j - 1] = Long.MAX_VALUE;

            arr[i][j] += Math.min(arr[i - 1][j], arr[i][j - 1]);
        }
    }

    System.out.println(arr[N][N]);
}

[congr]

// 처음 생각한 방법 - 헷갈리고 배열을 두개써서 비효율적이다
static long solve1(int N, int arr[][]) {
    long[][] re = new long[N + 1][N + 1];
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            if (i == 0 || j == 0)
                re[i][j] = 0;
            else if (i <= 1)
                re[i][j] = arr[i - 1][j - 1] + re[i][j - 1];
            else if (j <= 1)
                re[i][j] = arr[i - 1][j - 1] + re[i - 1][j];
            else
                re[i][j] = arr[i - 1][j - 1] + Math.min(re[i - 1][j], re[i][j - 1]);
        }
    }

    return re[N][N];
}