algospot_TRIANGLEPATH

TRIANGLEPATH

https://algospot.com/judge/problem/read/TRIANGLEPATH

문제

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

• 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있다.
• 맨 위의 숫자에서 시작해, 한 번에 한칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고한다.
• 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있다.
• 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하라.

풀이

모든 경로를 완전 탐색하면서, 불필요한 탐색의 경우를 제외하면 문제를 해결할 수 있다.

• getMax함수를 사용하여 완전 탐색한다.

  • 완전 탐색을 하면서 setInfo라는 2차원 배열에 합을 저장한다.

  • 완전 탐색을 하면서 "이전의 합 + 삼각형 현재 위치의 값"이 setInfo에 저장된 값보다 작은 경우

    • 기존에 저장돼있는 값이 더 크기 때문에 불필요한 탐색에 해당한다. 그러므로 해당 탐색을 더는 진행할 필요가 없다.

• 완전 탐색을 마친 뒤, 마지막 줄에서 최댓값 구하여 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int triangle[100][100];
int setInfo[100][100];
int n;
void getMax(int x, int y, int sum)
{
    if (x == n || y > x)
        return;
    if(setInfo[x][y] > sum + triangle[x][y])
        return;

    setInfo[x][y] = sum + triangle[x][y];
    getMax(x + 1, y, setInfo[x][y]);
    getMax(x + 1, y + 1, setInfo[x][y]);
}

int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int c;
    cin >> c;

    while (c--)
    {
        cin >> n;

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j <= i; ++j)
            {
                cin >> triangle[i][j];
            }
        }
        getMax(0, 0, 0);

        int maxValue = 0;
        for(int i=0; i<n; ++i)
        {
            maxValue = max(maxValue, setInfo[n-1][i]);

        }
        cout << maxValue << '\n';
        memset(setInfo, 0, sizeof(setInfo));
    }
    return 0;
}

결과