[Programmers 코딩 연습] 정수 삼각형 [Level 3]

문제(출처)-프로그래머스

첫 글이라 사용법이 서툴다...

알고리즘 기법

• 다이나믹 프로그래밍

설정

• 삼각형에서 각 숫자가 쓰여진 곳을 node(노드)라고 하자.
• 가장 위에 있는 삼각형은 (0,0), 즉 0행 0열이다.
• 각 행마다 첫번 째 숫자는 0열이다.
• node(i,j)는 i행 j열의 숫자를 의미한다.
• node(i,j)까지의 누적합 중 최댓값을 sum(i,j)라 하자.

설명

위 삼각형 그림에서 숫자 7, node(3,2)로 오는 길은 2가지로 나눌 수 있다.
이전 행의 숫자 8과 1 각각 두 노드를 지나야 한다.
그리고 이 두가지의 경로 중 더 큰 값이 node(3,2)까지의 최대 누적 합이다.
따라서 일반적으로 sum(i,j) = node(i,j) + max(node(i-1,j-1), node(i-1,j)) 와 같이 표현할 수 있다.

예외 사항

sum(i,j) = node(i,j) + max(node(i-1,j-1), node(i-1,j))로 표현할 수 있으나
위 삼각형 그림의 숫자 8과 0 노드처럼 각 행의 처음과 끝에서의 누적 합을 구할 때는 max값이 아닌 하나의 값으로 고정된다.
숫자 8 노드를 node(i,j)로 표현하면 node(i-1,j-1)이 존재하지 않고,
숫자 0 노드를 node(i,j)로 표현하면 node(i-1,j)가 존재하지 않기 때문이다.
따라서 j값이 0일 때와 j값이 (i-1)행의 마지막 인덱스 일 때 예외처리를 해야 한다.

(당연히 i가 0일 때, 즉 첫 노드는 sum(i,j) = node(i,j)로 예외로 포함된다.)

소스코드

python

def solution(triangle):
    # 메모이제이션용 리스트
    triangle_mem = []
    answer = 0
    
    # 메모이제이션 시작
        # previous row에 접근하기 위해 index 이용
    for i in range(len(triangle)):
        triangle_mem.append([])
        for j in range(len(triangle[i])):
            temp = triangle[i][j]
        
            if i == 0:
                triangle_mem[-1].append(temp)
                continue
            
            # Not exist: triangle_mem[i-1][j-1]
            if j == 0:
                temp += triangle_mem[i-1][j]
            # Not exist: triangle_mem[i-1][j]
            elif j == len(triangle_mem[i-1]):
                temp += triangle_mem[i-1][j-1]
            # (중간)최댓값 구하기
            elif triangle_mem[i-1][j-1] > triangle_mem[i-1][j]:
                temp += triangle_mem[i-1][j-1]
            else:
                temp += triangle_mem[i-1][j]
                
            triangle_mem[-1].append(temp)
    
    #(최종)최댓값 구하기
    for elem in triangle_mem[-1]:
        if answer < elem:
            answer = elem
            
    return answer

C++

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    vector<vector<int>> memo;
    
    for (int i = 0; i < triangle.size(); i++) {
        memo.push_back({});
        for (int j = 0; j < triangle[i].size(); j++) {
            memo[i].push_back(triangle[i][j]);
            
            if (i == 0)
                break;
            
            if (j == 0) {
                memo[i][j] += memo[i-1][j];
            }
            else if (j == triangle[i].size()-1) {
                memo[i][j] += memo[i-1][j-1];
            }
            else {
                memo[i][j] += (memo[i-1][j] > memo[i-1][j-1]) ? memo[i-1][j] : memo[i-1][j-1];
            }
        }
    }
    
    vector<vector<int>>::reverse_iterator it = memo.rbegin();
    
    for (int i = 0; i < it->size(); i++) {
        if (answer < (*it)[i])
            answer = (*it)[i];
    }
    
    // for (int i = 0; i < memo.back().size(); i++) {
    //     int temp = memo.back()[i];
    //     if (answer < temp)
    //         answer = temp;
    // }
    
    return answer;
}

느낀점

문제는 전형적인 다이나믹 프로그래밍 문제였다.
그러나 예외 사항을 처리할 때 조건문에 조건을 줄여서 코딩하려다가 가독성이 나빠지고 머리속에서 꼬여서 시간이 좀 걸렸다.
나중에 고치더라도 먼저 논리적으로 짜놓은 조건들을 그대로 옮겨서 코딩을 하고 난 후 조건을 합칠지 말지 결정하는 것이 효율적이라는 생각이 들었다.

(무엇보다 내가 글 재주가 참 없다는 생각이 든다.
쓰고 보니 글에 매력이 없다...)