[알고리즘] 동적계획법 - Triangle Path

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

Triangle Path

Triangle Path

• (0,0)부터 시작해서 [아래] 또는 [아래 우측]으로 이동 가능하다.
• 만나는 숫자를 모두 더한다.
• 더한 숫자를 최대가 되는 경로와 합을 구한다.

 

---

Triangle Path 연습 문제

6
1  2
3  7  4
9  4  1  7
2  7  5  9  4

 

위의 Triangle Path를 구하여라.

---

 

Triangle Path 문제 풀이

 

#include <iostream>
#include <vector>
using namespace std;
 
int N;
vector<vector<int>> board;
vector<vector<int>> cache;
vector<vector<int>> nextX; // 다음 경로
 
int path(int y, int x)
{
    // 기저 사항
    //if (y == N - 1)
    //    return board[y][x];
    if (y == N)
        return 0;
 
    // 캐시 확인
    int& ret = cache[y][x];
    if (ret != -1)  //초기화한 -1값이 아니니 경로를 구했다는 의미
        return ret;
 
    // 구하기
    // 경로 기록
    {
        int nextBottom = path(y + 1, x);
        int nextBottomRight = path(y + 1, x + 1);
        if (nextBottom > nextBottomRight)
            nextX[y][x] = x;
        else
            nextX[y][x] = x + 1;
    }
    // 적용
    return ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));
}
 
int main()
{
    board = vector<vector<int>>
    {
        {6},
        {1, 2},
        {3, 7, 4},
        {9, 4, 1, 7},
        {2, 7, 5, 9, 4}
    };
 
    N = board.size();
    cache = vector<vector<int>>(N, vector<int>(N, -1)); // 이중 벡터 -1로 초기화
    nextX = vector<vector<int>>(N, vector<int>(N));
 
    int ret = path(0, 0);
    cout << ret << endl;
 
    // 경로 만들기
    int y = 0;
    int x = 0;
    while (y < N)
    {
        cout << board[y][x] << " -> ";
 
        x = nextX[y][x];
        y++;
    }
}

 

// 적용

현재 위치:                              board[y][x] 

[아래]로 가는 경우:                path(y + 1, x)          
[아래 우측]으로 가는 경우:    path(y + 1, x + 1)

return ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));

[아래], [아래 우측] 중 더 큰 값을 현재 위치에 더해준 후 return한다.

 

---

 

 

콘솔 실행