#9184 신나는 함수 실행

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

9184번: 신나는 함수 실행

실버2의 문제였다. 재귀함수를 저렇게나 많이 돌리는데 시간 제한이 1초??? 이건 dp다. 그리고 재귀를 쓰는 함수면 일단 dp를 고민해보는것도 좋은것 같다. 계산 시간을 확 줄여주는데 도움을 주니까~

 

#include <iostream>
using namespace std;

int memo[51][51][51];

int w(int a,int b,int c){
  if(a<=0 || b<=0 || c<=0)
    return 1;
    
  else if(a>20 || b>20 || c>20)
    return w(20,20,20);
    
  else if(a<b && b<c){
    if(memo[a][b][c]!=0)
      return memo[a][b][c];
    else if(memo[a][b][c]==0){
      memo[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
      return memo[a][b][c];
    }
  }

  else{
    if(memo[a][b][c]!=0)
      return memo[a][b][c];
    else if(memo[a][b][c]==0){
      memo[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
      return memo[a][b][c];
    }
  }
}

int main()
{
  //freopen("input.txt","r",stdin);
  int a,b,c;
  int ans=0;
  while(true){
    cin>>a>>b>>c;
    if(a==b&&b==c && a==-1){
      break;
    }
    else{
      ans=w(a,b,c);
      cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<ans<<'\n';
    }
  }
}

일단 문제에서 시키는 대로 재귀함수를 구현했다. 근데 무지성으로 구현하면 시간이 10억년 걸리기때문에 메모이제이션을 적극 활용했다. 재귀함수 내에서 또다시 함수를 호출 하는 부분에서 memo배열에 값이 0이라면 값이 계산된 적이 없는 것이기 때문에 계산을 하고 난 후 return 해주었고, 계산한 적이 있어서 값이 0이 아니라면 그대로 return 해 주었다.

 

그리고 처음에 if(a==b==c && a==-1) 이렇게 썼다가 while문이 무한루프에 빠지길래 뭐가 문제인지 모르고 한참 헤맸었다. 유도리 있게 a==b==c 이런건 좀 해주면 안되나? 아무튼... 문제 자체는 쉬웠다!✌