백준 신나는 함수 실행 [c++]

신나는 함수 실행 실버2

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

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) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

풀이

• 주어진 제귀함수를 개선하는 문제.
• w(5,5,5)도 실행시간이 오래걸려 결과가 나오지 않았다.
• 일단 중간에 반복되어 쓰이는 값이 존재해 메모이제이션 적용해봄.
• 해결.

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int stored[21][21][21];

int w(int a, int b, int c){
    // cout << "w(" << a << " " << b << " " << c << ")" << endl;
    if(a <= 0 || b <= 0 || c <= 0){
        return 1;
    } 
    if(a > 20 || b > 20 || c > 20){
        return w(20,20,20);
    } 

    if(stored[a][b][c]){
        return stored[a][b][c];
    }
    
    if( a < b && b < c){ 
        stored[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        return stored[a][b][c];
    } else{
        stored[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 stored[a][b][c];
    }
}

int main(){
    // cout << w(5, 5, 1) << endl;
    string str;
    string end_point = "-1 -1 -1 ";
    getline(cin, str);
    str += " ";
    while(end_point.compare(str) != 0){
        string delim = " ";
        vector<string> words;

        size_t pos = 0;
        while((pos = str.find(delim)) != string::npos)
        {
            words.push_back(str.substr(0, pos));
            str.erase(0, pos + delim.length());
        }

        int num[3];
        for(int i = 0; i < 3; i++)
        {
            num[2-i] = stoi(words.back());
            words.pop_back();
        }
        // cout << num[0] << num[1] << num[2] << endl;
        cout << "w(" << num[0] << ", " << num[1] << ", " << num[2] << ") = ";
        cout << w(num[0], num[1], num[2]) << endl;
        getline(cin, str);
        str += " ";
    }


    return 0;
}

총평

• 메모이제이션 한방으로 해결되어 실버인듯.
• 그런데 입력을 string으로 받아 파싱한 후 int로 변환했는데 생각해보니 그냥 int로 받아 사용해도 됬을 것 같다.

• ps
• 구현