(9184) 신나는 함수 실행

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

단계별로 풀어보기

21단계(동적 계획법 1) 2번째

 

 

 

동적계획법에서 주로 사용하는 기법인 메모이제이션에 대해 배우는 문제.

메모이제이션이란 구한 결과를 메모리에 저장하고 필요할 때 꺼내 써 중복 계산을 방지하는 기법이다.

재귀함수 w를 그대로 구현하면 엄청난 시간이 걸리지만 w(a,b,c)의 값을 구할 때 따로 저장한 뒤 나중에 해당 함수를 다시 호출할 때 계산할 필요 없이 바로 저장한 값을 가져오면 된다. 이러면 이미 저장한 값을 찾을 때는 O(1)이 소요되고 새로운 값을 구할 때만 계산하면 되므로 시간 복잡도가 값을 저장하는 배열의 크기만큼 획기적으로 줄어들게 된다.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int w[21][21][21]= {0, };
  
  auto func= [&](auto self, int a, int b, int c) -> int {
    if(a<=0 || b<=0 || c<=0)  return 1;
    if(a>20 || b>20 || c>20)  return self(self,20,20,20);
    
    if(w[a][b][c])  return w[a][b][c];
    
    if(a<b && b<c){
      w[a][b][c]= self(self,a,b,c-1)+self(self,a,b-1,c-1)-self(self,a,b-1,c);
    }else{
      w[a][b][c]= self(self,a-1,b,c)+self(self,a-1,b-1,c)+self(self,a-1,b,c-1)-self(self,a-1,b-1,c-1);
    }
    
    return w[a][b][c];
  };
  
  while(true){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    if(a==-1 && b==-1 && c==-1)  break;
    
    cout << "w(" << a << ", " << b << ", " << c << ") = " << func(func, a, b, c) << "\n";
  }
  
  return 0;
}