종만북 삼각형 최대 경로 카운트 (TriPathCnt) C++ 풀이 (코드제공)

1. 문제 설정 확인

저번에 했던 삼각형의 최대 경로에서 한발자국 더 나아가 그 최대 경로의 개수가 얼마인지 카운트 해야한다.

설명 작성 예정

3. 해답 코드

#include <iostream>
#include <string.h>
using namespace std;

int n;
int size;
int cache[100][100];
int triangle[100][100];
int cache2[100][100];

int path(int y, int x){
    if (y == size - 1)
        return triangle[y][x];
    int& ret = cache2[y][x];
    if (ret != -1)
        return ret;
    return ret = max(path(y + 1, x), path(y + 1, x + 1)) + triangle[y][x]; // 부분 경로의 최대치를 구한다.
}

int countPath(int y, int x){
    if (y == size-1) return 1;
    int& ret = cache[y][x];
    if(ret != -1) return ret;
    ret = 0;
    if(path(y+1, x+1) >= path(y+1, x)) ret += countPath(y+1, x+1);
    if(path(y+1, x+1) <= path(y+1, x)) ret += countPath(y+1, x);
    return ret;
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++){
        memset(cache, -1, sizeof(cache));
        memset(cache2, -1, sizeof(cache2));
        memset(triangle, 0, sizeof(triangle));
        cin >> size;
        for(int j = 0; j < size; j++){
            for(int k = 0; k <= j; k++){
                cin >> triangle[j][k];
            }
        }
        int result = countPath(0, 0);
        cout << result << endl;
    }
}

슬슬 DP문제에서의 재귀 호출이 뭐가 뭔지 잘 모르겠는 분들이 많을 것 같아요. 제 팁은, 재귀 호출과정에서 도대체 뭐가 일어나는지를 너무 생각하지 않는 게 좋단겁니다. 재귀 호출은 그 다음 호출, 또 그 다음 호출을 거쳐 기저조건에 도달했을 때 값을 return받습니다. 당연히 저희가 그 다음 언젠가의 재귀호출 과정에서 답을 return받을 걸 가정하고 쓰는 기법이니까, 정확한 기저 조건의 설계만 있다면 마법처럼 동작하기 마련이기에, 어떻게 값을 return해 줄건지, 기저 조건은 어떻게 설계할건지가 가장 중요합니다!

Source

종만북, 2022.07.22
CLion