Lv.3 [동적계획법] - 정수 삼각형

---

[ 문제 링크 ]

프로그래머스 Lv3. 정수 삼각형

 

[ 문제 설명 이미지 ]

 

동적계획법

큰 문제를 작은 문제로 나누어 푸는 방법.
복잡한 문제를 풀기 위해 작게 조각내어 문제를 풀고 합치면 된다.

 

정수삼각형

숫자로 구해진 삼각형이 있고 위에서부터 대각선으로만 내려올 수 있다.
내려오면서 숫자를 더했을 때 어떤 경로로 이동했을 때 가장 큰 숫자가 나오는지 가장 큰 최대값을 구하는것이 문제이다.
굉장히 많은 경우의수가 나올수 있기 때문에 어렵게 느껴질 수 있지만, 이중 하나만 때어놓고 생각해보면
7에서 3으로 가는것과 7에서 8로 가는것 둘중 어느것이 최대값으로 가는것인지 생각해보면 굉장히 단순하다.
이 작은 조각의 단위가 여러개 있는것 뿐이다.
중간의 경우
 8 1 0
2 7 4 4
처음 2는 8에서부터 내려오는 경우 뿐이니 2 + 8 = 10이 된다.
다음 7은 8과 7이 더해지는경우, 1과 7이 더해지는 경우가 있지만 8과 1중에서 8이 최대값이므로 7 + 8 = 15가 된다.
다음 4는 1과 4가 더해지는 경우, 0과 4가 더해지는 경우가 있지만 1과 0중에서 1이 최대값이므로 1 + 4 = 5가 된다.
다음 4는 0에서부터 내려오는 경우 뿐이니 0 + 4 = 4가 된다.
10 15 5 4 이렇게 특정 한 조건만 놓고 봤을 때 어느 경우가 최대값을 갖는지 최대값을 갖는 경우를 택한다는 단순한 논리로 구성되어있다.
이 작업을 최상단에서부터 최하단까지 순차적으로 구하면서 최종으로 얻은 숫자들의 최대값을 구하면 되는 문제이다.

---

[풀이 1] 탑/다운 방식

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0; // max
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length ; j++) {
                /* i는 위에서 아래방향 j는 왼쪽에서 오른쪽방향 */

                if (j == 0) { //[좌측 끝] 이전 행이 left는 없고 rigt만 있는 경우
                    triangle[i][j] =  triangle[i][j] + triangle[i-1][j];
                } else if (i == j) { // [우측 끝] 이전 행이 right는 없고 left만 있는 경우
                    triangle[i][j] = triangle[i][j] + triangle[i - 1][j - 1];
                } else {
                    int left = triangle[i][j] + triangle[i-1][j-1]; // 2차원 케이스의 왼쪽값
                    int right = triangle[i][j] + triangle[i-1][j]; // 2차원 케이스의 오쪽값
                    triangle[i][j] = Math.max(left, right);
                }
                answer = Math.max(answer, triangle[i][j]);
            }
        }
        return answer;
    }
}

 

위에서부터 아래쪽으로 내려오면서 각 행에 해당하는 케이스에 대해 좌측부터 우측방향으로 탐색한다.

아래행의 각 노드들로 부터 이전행의 대각선에 해당하는 노드를 더해 나가야 하므로, 탐색의 기준은 두번째 케이스부터 시작한다.

이때, 각 케이스의 좌측 첫번째 노드와 우측 마지막노드에 해당하는값은 이전행에 대해 각각 좌측노드와 우측노드가 존재하지 않으므로 단순히 바로 위 방향에 존재하는 각각의 첫/끝 노드에 더해준다.

 

즉, 현재 행의 각 노드 기준 이전 행의 좌측노드, 우측노드 모두 가지고있는 케이스에 대해서

현재 노드와 이전행의 두 노드에 대한 각각의 합을 구하고 비교하여 그중 최대 값을 도출해낸다.

만약 첫 노드와 끝 노드라면 이전 행에 각자의 쌍이 존재하지 않기 때문에 일치하는 대각선 방향으로 그대로 더해 나간다.

 

각 케이스(행)별로 위에서 아래로 순차적으로 루프를 돌며 계산해 나간다.

마지막에 남은 4개의 최대값중 가장 큰 값을 반환한다.

가장 첫 최대값은 10, 15 중 15

두 번째 최대값은 18, 16,  15 중 16

세 번째 최대값은 20, 25, 20, 19 중 25

네 번째 최대값은 24, 30, 27, 26, 24 중 30

최종적으로 가장 큰 값은 30이 된다.

 

케이스(행)별로 좌측에서 우측으로 노드가 넘어갈 때 마다 이전행의 대각선 쌍에 대한 각각의 합의 최대값을 구하고,

최대값이 구해질 때 마다 이전노드에 대한 값과 비교해서 그중 최대값을 최종 반환할 값으로 반복 저장해 나간다.

 

---

[풀이 2] 바텀/업 방식

import java.util.stream.IntStream;

public class Solution {

    public int solution(int[][] triangle) {
        for (int i = triangle.length-2; i >= 0 ; i--) { /* 1번 과정 때문에 마지막케이스보다 한단계 위에서부터 반복을 시작한다. */
            for (int j = 0; j < triangle[i].length; j++) {
                /* 1. 바로 위 케이스를 기준으로 아래 케이스를 각각 누적한 값의 최대값을 바로 위 케이스에 초기화 */
                int left = triangle[i][j] + triangle[i+1][j];
                int right = triangle[i][j] + triangle[i+1][j+1];
                triangle[i][j] = Math.max(left, right);
            }
        }
        return triangle[0][0];
    }

}

 

가장 마지막 케이스(행) 부터 시작하여 거꾸로 더해나간다.

바로 이전 케이스(행)을 기준으로 현재 케이스(케이스)에 대한 대각선 쌍을 더한 뒤 그 두 값중 최대값을 더했던 이전 케이스(행)에 초기화 하며 반복하여 올라간다.

 

루프상에서는 이전 케이스(행)을 처음부터 선택해야 하므로 한단계 위에서부터 반복할 수 있도록 index값을 1 더 감소한 상태에서 시작하고, 누적합 연산을 할 때 index값을 1 더함으로써 현재 케이스(행)에 접근한다.

---

[나의 풀이] 정답 (탑/다운 방식)

public class Solution {

static int answer = 0;
    public int solution(int[][] triangle) {
        int answer = 0;
        /* 2차 배열요소 마지막 요소부터 추출 */
        for (int i = triangle.length-1; i >= 0; i--) {
            for (int j = triangle[i].length-1; j >= 0; j--) {
                if(i == 0 && j == 0) {
                    answer = triangle[i][j]; // [0][0] 까지 1번에 대한 최대값 누적 처리가 되었으므로 해당 값을 최종 answer에 저장후 종료한다.
                    break;
                }
                if(j == 0) break; //아래 최대값 누적 처리가 다음 루프에서 이전 배열 요소 길이가 더 작아지기 때문에 마지막 최대값 누적 연산을 진행하지 않음
                answer = Math.max(triangle[i][j - 1], triangle[i][j]);
                triangle[i-1][j-1] += answer; // 1. 이전 1차 배열 요소에 구해진 최대값을 각각 더해준다.
            }
        }
        return answer;
    }
}

 

가장 아래 케이스의 우측 노드부터 차례로 이전노드와 현재노드에 대한 최대값을 구하고,

그 값을 이전 케이스의 우측노드부터 매핑되는 위치에 차례대로 더해준다.

이때, 이전 케이스는 현재 케이스보다 노드 갯수가 1개 적으므로, 현재 케이스의 첫번째 노드에 도달했을 때 최대값을 도출하지 않고 두번째 반복문을 빠져나가 다음 케이스에 접근한다.

배열 인덱스가 0,0 일 경우 가장 상단노드를 말한다.

따라서 모든 케이스에 대한 처리가 끝났을 경우 이므로 현재 최 상단 까지 누적합으로 구해진 최종 노드값을 반환한다.

---