[백준] 9184번: 신나는 함수 실행 풀이 및 해설(C++)

 

문제 이미지

풀이

함수의 규칙에 따라 재귀함수로 출력해야 한다.

재귀함수로 출력하되, 이미 저장된 값은 동적계획법으로 바로 출력할 수 있게 하면 된다.

하지만, 이 문제에서는 재귀함수 말고 반복문을 통한 동적계획법으로도 출력이 가능해 재귀함수를 사용하지 않는 방식으로 풀었다.

비슷한 문제가 나올 경우, 재귀함수를 이용해 푸는 것을 추천한다. 

 

 

해답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int arr[101][101][101];


int main(){
    int a=1,b=1,c=1;
    while(!(a==-1&&b==-1&&c==-1)){
    cin>>a>>b>>c;
    if(a==-1&&b==-1&&c==-1){
        break;
    }
    if(a<=0||b<=0||c<=0){
        cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<'1'<<'\n';
        continue;
    }
     if(a>20||b>20||c>20){
        cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<"1048576"<<'\n';
        continue;
    }
    for(int i=0;i<a+1;i++){
        for(int j=0; j<b+1; j++){
            for(int k=0; k<c+1; k++){
                if(i==0 || j==0 || k==0){
                    arr[i][j][k]=1;
                }
                else if(i<j && j<k){
                    arr[i][j][k]=arr[i][j][k-1]+arr[i][j-1][k-1]-arr[i][j-1][k];
                }
                else{
                    arr[i][j][k]=arr[i-1][j][k]+arr[i-1][j-1][k]+arr[i-1][j][k-1]-arr[i-1][j-1][k-1];
                }
            }
        }
    }
    cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<arr[a][b][c]<<'\n';
    
    }
    return 0;
}