백준 9184번(신나는 함수 실행) c++ 풀이

https://www.acmicpc.net/problem/9184

 

주어진 재귀 함수를 보면,

 

특징 1) a, b, c 셋 중 하나가 0 이하일 때 1

 

특징 2) a, b, c 셋 중 하나가 20 초과일 때 w[20][20][20]

 

그리고 나머지 케이스에서 재귀 호출을 할 때

특징 3) 인수가 a, b, c, a - 1, b - 1, c - 1 에 속한다.

 

dp 테이블 채우기 좋자나..

특징 1로 베이스를 깔면 나머지 테이블은 채울 수 있다.

 

-50 ≤ a, b, c ≤ 50 라고 제한이 나와있긴 하지만 0 이하이면 0으로 치환시키고 20 초과이면 20으로 치환시키면 되니까

테이블은 인덱스 0부터 20까지만 필요하다.

 

이중 for문으로 베이스 깔아주고, 3중 for문 돌면서 나머지 테이블 채워준다.

답 출력할 때는 테이블에 저장된 값 활용할 수 있도록 a, b, c를 치환해주면 끝..

 

출력은 귀찮아서 printf 썼당

#include <iostream>

using namespace std;

int w[21][21][21];

void makeTable(){
    for(int i=0; i<=20; i++){
        for(int j=0; j<=20; j++){
            w[0][i][j] = w[i][0][j] = w[i][j][0] = 1;
        }
    }
    
    for(int i=1; i<=20; i++){
        for(int j=1; j<=20; j++){
            for(int k=1; k<=20; k++){
                if(i < j && j < k){
                    w[i][j][k] = w[i][j][k - 1] + w[i][j - 1][k - 1] - w[i][j - 1][k];
                }
                else{
                    w[i][j][k] = w[i - 1][j][k] + w[i - 1][j - 1][k] + w[i - 1][j][k - 1] - w[i - 1][j - 1][k - 1];
                    
                }
            }
        }
    }
    
    return;
}
int ans(int a, int b, int c){
    if(a <= 0 || b <= 0 || c <= 0){
        a = b = c = 0;
    }
    if(a > 20 || b > 20 || c > 20){
        a = b = c = 20;
    }
    
    return w[a][b][c];
}

int main(){
    makeTable();
    
    int a, b, c;
    while(true){
        cin >> a >> b >> c;
        
        if(a == -1 && b == -1 && c == -1) break;
        
        printf("w(%d, %d, %d) = %d\n", a, b, c, ans(a, b, c));
    }
    
    return 0;
}