Koala - 2기/A반

[9184번]신나는 함수 실행

알 수 없는 사용자 2021. 1. 21. 15:14

www.acmicpc.net/problem/9184

 

9184번: 신나는 함수 실행

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

www.acmicpc.net

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위와 같은 재귀함수를 그대로 구현했을 때 시간이 매우 오래걸리므로

DP의 메모이제이션 기법을 이용하여 풀면 되는 문제였습니다.

 

  1. 인수 중에 음수가 있으면 return 1
  2. 배열에 저장된 값이 있으면 바로 return
  3. 배열에 저장된 값이 없으면 계산 후 return 

전체코드

더보기 
#include <iostream>

using namespace std;

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

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

int main() {
    int a,b,c;

    while(1){
        cin>>a>>b>>c;

        if(a==-1&&b==-1&&c==-1) {
            return 0;
        }

        cout << "w(" << a << ", " << b << ", " << c << ") = ";
        cout << dp(a, b, c);
        cout << "\n";
    }
    return 0;
}