BOJ | Silver 1/1932/정수 삼각형

독자님은 코딩테스트 문제를 풀면서 밤을 새본 적이 있나요? 저는 있습니다. :)...
독자님은 밤을 새시지 마시라는 의도로 본 글을 쓰게 되었습니다.
사실 구글링만 해보면 되는 결과를 안보고 풀겠다고 고집을 부리다가 또 밤을 새버렸네요. 지난 6월에 주에 한번 꼴로는 밤을 새본 것 같습니다. 이 문제도 그러한 문제 중 한 문제라고 보시면 되겠습니다.
정말 간단하게 풀어지는 풀이법은 dp로 이차원 배열로 정의해서 메모이제이션 방식으로 푸는겁니다. 그런데 저는 1차원 배열인 dp로 풀기 위해서 많은 시간을 사용했습니다. 고집을 포기하는 순간 행복해지는 거더라구요!_! 어쨌든.
https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

1. 문제 이해

위 그림처럼 정수들이 파스칼의 삼각형의 형태처럼 놓여있습니다. 맨 위층에 위치한 7을 시작으로 좌측 대각선 혹은 우측 대각선 아래로 내려오면서 값을 더해가는데, 값을 더한 결과는 같은 방식으로 더한 합들 중 가장 큰 값이어야 하고, 그 최댓값을 출력하면 됩니다. 
그래서 저는 이렇게 생각했습니다. 

가장 윗 값을 기준으로 내려오면서 인덱스로 값을 더해주고, 더해준 값을 각각 dp에 담아서 메모이제이션 방식으로 값을 더해나가면서 가장 큰 값을 찾으면 된다고 말입니다. 아이디어는 금방 생각해냈지만, dp를 1차원 배열로 정의했다가 아주 호되게 혼났습니다. (새벽 내내 펜으로 끄적이면서 풀었습니다) 어찌됐든 dp를 2차원 배열로 다시 정의 한 뒤 문제를 해결하였습니다. 각 인덱스의 대각선 위에 해당하는 인덱스를 접근하는 방법을 결국 찾지 못했습니다. 풀었으니까 문제는 없지만, 고민의 시간을 좀 더 줄이는 현명한 선택을 해보도록 노력...해보겠스빈다.

 
 

2. 로직

2-1) 로직 플로우 
로직은 메모이제이션 방식을 활용하는 것입니다. 배열의 현재 위치와 대각선 윗 값들의 합 중 최댓값을 dp의 해당 인덱스의 값에 매핑해주고 나서 N번째 행의 값들만 가져다가 가장 큰 값을 찾아내 출력하는 것입니다.
2-2) 로직 상세
1) Scanner로 값을 읽어들인다.
2) 가장 먼저 입력된 값을 N으로 정의한다. (DP에서 N+1행 N+1열로 자주 초기화하여 대문자로 적었습니다.)
3) dp 배열과 입력 데이터를 담을 inputArr배열을 2차원 배열로 정의해줍니다. 이때 dp와 inputArr 모두 인덱스 접근을 직관적으로 하기 위해서 N+1개의 배열로 초기화합니다.
4) 이중 for문으로 입력 데이터를 모두 담습니다. 그러면 이차원 배열 형태의 입력값을 담는 inputArr이 일단 만들어집니다. 이 배열은 위 정수 삼각형의 값을 불러들이는 자원이기 때문에 dp 인덱스와 1:1로 매핑이 되어야 하므로 각 위치에 값이 정확하게 담기도록 합니다. 이때 주의할 점은 담는 데이터의 인덱스는 j번째인 반면 읽어들이는 데이터의 인덱스는 j-1번째인 것입니다.
5) dp[1][1] 값은 inputArr[1][1] 값으로 초기화 합니다. 그리고 나서 누적 합 계산을 시작합니다.
6) 이중 for문으로 dp에 인덱스로 접근하는데, dp에 담긴 값은 해당 인덱스의 대각선 왼쪽 위 혹은 오른쪽 위의 합에 inputArr의 해당 인덱스에 담긴 값을 더한 값입니다. 그래서 왼쪽 대각선 위 + 현재 위치의 값과 오른쪽 대각선 위 + 현재위치의 값 중 더 큰 값을 Math.max 메서드로 비교한 뒤 dp에 담아줍니다. 그런데 이때 위 층에서 한쪽 방향으로만 내려오는 인덱스의 값들은 이와 같이 계산해도 상관이 없습니다. 현재 위치에서 가장 큰 값이 dp에 저장될 것이므로, dp의 왼쪽 위나 오른쪽 위만 존재하는 인덱스들은 비교하는 값이 0이기 때문에 각 위치에서 항상 최댓값만 담을 수 있습니다.
7) 마지막 줄인 N번째 행의 dp 값을 가져와서 Math.max 메서드로 최댓값을 찾습니다.
8) 최댓값 출력
 

3. 구현

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        int[][] inputArr = new int[N + 1][N + 1];
        int[][] dp = new int[N + 1][N + 1];
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            String[] temp = sc.nextLine().split(" ");
            for (int j = 1; j <= temp.length; j++) {
                inputArr[i][j] = Integer.parseInt(temp[j - 1]);
            }
        }

        dp[1][1] = inputArr[1][1];

        for (int i = 2; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = Math.max(dp[i - 1][j] + inputArr[i][j], dp[i - 1][j - 1] + inputArr[i][j]);
            }
        }

        int max = 0;
        for (int i = 0; i <= N; i++) {
            max = Math.max(max, dp[N][i]);
        }

        System.out.println(max);
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

같은 문제가 프로그래머스에도 있습니다 :-) 두 번 풀어보시길 바랄게요-!
문제와 관련한 질문은 댓글로 남겨주시면 감사드리겠습니다! :)