algospot TRIPATHCNT

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

http://jaimemin.tistory.com/316?category=985009에서 최대 경로의 최적해를 구한 적이 있기 때문에 비교적 쉽게 문제를 풀 수 있었습니다.

/*

TRIANGLEPATH에서는 최대 경로의 최적해만을 구했다.

이번에는 최대 경로의 개수를 구하시오.

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int height; //삼각형의 높이

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

int cache[100][100];

int countCache[100][100];

 

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]; //(아래로 내려가거나 오른쪽 아래) + 현재 위치

}

 

//(y, x)에서 시작해서 맨 아래줄까지 내려가는 경로 중 최대 경로의 개수 반환

int count(int y, int x)

{

        //기저 사례: 맨 아랫줄에 도달한 경우

        if(y==height-1)

               return 1;

        //메모이제이션

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

        if (result != -1)

               return result;

        result = 0;

        //아래로 내려가는 것보다 오른쪽 아래 대각선으로 가는 경로가 더 클 경우

        if (path(y + 1, x + 1) >= path(y + 1, x))

               result += count(y + 1, x + 1);

        //아래로 내려가는 경로가 더 클 경우

        if (path(y + 1, x + 1) <= path(y + 1, x))

               result += count(y + 1, x);

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case > 50 || test_case < 0)

               exit(-1);

 

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

        {

               cin >> height;

               if (height < 2 || height>100)

                       exit(-1);

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

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

                       {

                              cin >> triangle[j][k];

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

                                      exit(-1);

                       }

               memset(cache, -1, sizeof(cache));

               memset(countCache, -1, sizeof(countCache));

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

        }

        return 0;

}

개발환경:Visual Studio 2017

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

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