[백준 9184] 신나는 함수 실행 (C++)

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

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)

이 문제는 -50~50 범위의 정수인 a,b,c가 주어지면 w(a,b,c)를 구해서 출력하는 문제다.

 

접근방법

입력받는대로 계산할 수도 있지만 그러면 재귀함수를 너무 많이 호출하게 돼서 시간복잡도가 커지는 문제 -> 그래서 DP로 풀어야 하는데

이번에도 다 저장해두고 사용하는 방법으로 풀었다. 그래도 계산하는 횟수가 101*101*101 정도라 시간초과가 안나는 것 같다.

3차원 배열 arr[a][b][c]에 3중 반복문을 돌면서 차례차례 값을 저장한다. 숫자 하나라도 0 이하면 함숫값이 1이기 때문에 차곡차곡 쌓아서 그 다음부터는 바로 꺼내쓸 수 있게 된다.

그런데 이 방식대로 풀면 1 1 21이 호출될때 처음으로 w(20,20,20) 값을 찾게 되는데 이때는 아직 w(20,20,20)에 값이 없기 때문에 초기화 값인 0이 할당된다. 그러면 20 20 20 전까지 w(20,20,20)을 호출하는 경우는 모두 0이 할당됨

그래서? 어차피 101*101*101 나 2*101*101*101일 것 같아서 두번 돌려보니 통과됨..

더 좋은 방법이 있겠지 싶어서 찾아봤는데 로직이 달라서 그냥 안고치고 올립니다.. 허허

 

소스코드

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int main(){
    
    int arr[101][101][101];
    int _a, _b, _c;
    
    for(int a = 0; a < 101; a++){
        for(int b = 0; b < 101; b++){
            for(int c = 0; c < 101; c++){
                _a = a-50;
                _b = b-50;
                _c = c-50;
                if(_a <= 0 || _b <= 0 || _c <= 0)
                    arr[a][b][c] = 1;
                else if(_a > 20 || _b > 20 || _c > 20)
                    arr[a][b][c] = arr[70][70][70];
                else if(a < b && b < c)
                    arr[a][b][c] = arr[a][b][c-1] + arr[a][b-1][c-1] - arr[a][b-1][c];
                else
                    arr[a][b][c] = arr[a-1][b][c] + arr[a-1][b-1][c] + arr[a-1][b][c-1] - arr[a-1][b-1][c-1];
            }
        }
    }
    
    for(int a = 0; a < 101; a++){
        for(int b = 0; b < 101; b++){
            for(int c = 0; c < 101; c++){
                _a = a-50;
                _b = b-50;
                _c = c-50;
                if(_a <= 0 || _b <= 0 || _c <= 0)
                    arr[a][b][c] = 1;
                else if(_a > 20 || _b > 20 || _c > 20)
                    arr[a][b][c] = arr[70][70][70];
                else if(a < b && b < c)
                    arr[a][b][c] = arr[a][b][c-1] + arr[a][b-1][c-1] - arr[a][b-1][c];
                else
                    arr[a][b][c] = arr[a-1][b][c] + arr[a-1][b-1][c] + arr[a-1][b][c-1] - arr[a-1][b-1][c-1];
            }
        }
    }

    int a,b,c;
    cin >> a >> b >> c;

    while( a != -1 || b != -1 || c != -1 ){
        printf("w(%d, %d, %d) = %d\n", a, b, c, arr[a+50][b+50][c+50]);
        cin >> a >> b >> c;
    }
    
    return 0;
}