algospot TRIANGLEPATH

문제 링크입니다: https://algospot.com/judge/problem/read/TRIANGLEPATH

동적계획법을 이용해서 문제를 풀었습니다.

/*

삼각형으로 배치된 자연수들이 있다.(정사각을 왼쪽 위에서 오른쪽 아래 대각선 기준으로 잘랐을 때 아래 부분)

맨 위의 숫자에서 시작해서, 한번에 한 칸씩 아래로 내려가

맨 아래 줄까지 닿는 경로를 만들려고 한다.

경로는 아래줄로 내려갈 때마다 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있다.

이 때 모든 경로 중 숫자의 합을 최대화하는 경로는?

또한 경로에 포함된 숫자들의 최대 합은 얼마인가

*/

#include <iostream>

#include <cstring> //memset

#include <algorithm>

using namespace std;

 

//MAX_NUMBER:한 칸에 들어갈 숫자의 최대치

//const int MAX_NUMBER = 100000;

//int cache[100][100][MAX_NUMBER * 100 + 1];

 

int height; //삼각형의 높이

int triangle[100][100]; //삼각형 표현을 위해

int cache[100][100];

 

/*

//완전탐색

//(y,x) 위치까지 내려오기 전에 만난 숫자들의 합이 sum일 때

//맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로 반환

int path1(int y, int x, long sum)

{

        //기저 사례:맨 아래 줄까지 도달했을 경우

        if (y == height - 1)

               return sum + triangle[y][x];

        //메모이제이션

        int &result = cache[y][x][sum];

        if (result != -1)

               return result;

        sum += triangle[y][x];

        return result = max(path1(y + 1, x + 1, sum), path1(y + 1, x, sum));

}

*/

 

//메모이제이션

//(y,x) 위치부터 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로의 합 반환

int path(int y, int x)

{

        //기저 사례

        if (y == height - 1)

               return triangle[y][x];

        //메모이제이션

        int &result = cache[y][x];

        if (result != -1)

               return result;

        return result = max(path(y + 1, x), path(y + 1, x + 1)) + triangle[y][x]; //(아래로 내려가거나 오른쪽 아래) + 현재 위치

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 0 || test_case>50)

               exit(-1);

       

        for (int i = 0; i < test_case; i++)

        {

               memset(cache, -1, sizeof(cache)); //캐시 초기화

               cin >> height;

               if (height < 2 || height > 100)

                       exit(-1);

               for (int i = 0; i < height; i++)

                       for (int j = 0; j < i + 1; j++)

                       {

                              cin >> triangle[i][j];

                              if (triangle[i][j] < 1 || triangle[i][j]>100000)

                                      exit(-1);

                       }

               cout << path(0, 0) << endl << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략