[ALGOSPOT] 알고스팟 TRIANGLEPATH 삼각형 위의 최대 경로(C++, Python)

www.algospot.com

[ALGOSPOT] 알고스팟 TRIANGLEPATH 삼각형 위의 최대 경로

(C++, Python)

(글쓴날 : 2020.05.01)

 

---

* ALGOSPOT, 알고스팟 TRIANGLEPATH 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 TRIANGLEPATH 삼각형 위의 최대 경로

---

1) 문제

문제 링크 : https://www.algospot.com/judge/problem/read/TRIANGLEPATH

algospot.com :: TRIANGLEPATH

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

삼각형 형태로 배치되는 2차원 배열이 주어지고, 맨 위의 숫자부터 자신의 아래 혹은 아래의 오른쪽으로 수를 합쳐가며 내려갈 수 있을 때, 가능한 모든 경로 중 최대 합을 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

memoization을 위해 따로 테이블을 만들지 않아도 되며, 주어지는 값을 모두 입력받은 후, 두 번째 줄부터 탐색할 인덱스를 기준으로 위에서 가능한 경로 중 합했을 때 가장 큰 결과를 해당 인덱스에 다시 덮어씌우는 식으로 문제를 해결했습니다.

이 문제는 각 PS 사이트마다 동적 계획법 초반부에 항상 출제되는 기본 중의 기본 문제인 것 같습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int triangle[101][101];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int C = 0;
    cin >> C;
 
    int n = 0;
    while (C--)
    {
        cin >> n;
        memset(triangle, 0, sizeof(triangle));
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i + 1; j++)
            {
                cin >> triangle[i][j];
 
                if (i >= 1)
                {
                    if (j == 0)
                        triangle[i][j] += triangle[i - 1][j];
                    else if (j == i)
                        triangle[i][j] += triangle[i - 1][j - 1];
                    else
                        triangle[i][j] += max(triangle[i - 1][j], triangle[i - 1][j - 1]);
                }
            }
        }
 
        cout << *max_element(&triangle[n - 1][0], &triangle[n - 1][n + 1]) << "\n";
    }
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
C = int(input())
 
for _ in range(C):
    n = int(input())
    triangle = [list(map(int, input().split())) for _ in range(n)]
 
    for i in range(1, n):
        for j in range(i + 1):
            if j == 0:
                triangle[i][j] += triangle[i - 1][j]
            elif j == i:
                triangle[i][j] += triangle[i - 1][j - 1]
            else:
                triangle[i][j] += max(triangle[i - 1][j], triangle[i - 1][j - 1])
 
    print(max(triangle[-1]))

---