[BOJ-9184][C++] 신나는 함수 실행

문제

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

다음과 같은 재귀함수 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)를 출력하는 프로그램을 작성하시오.

 

입력

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

 

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

 

제한

• -50 ≤ a, b, c ≤ 50

 

예제 입력 1

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

 

예제 출력 1

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

 

출처

ICPC > Regionals > North America > Pacific Northwest Regional > 1999 Pacific Northwest Region Programming Contest C번

 

알고리즘 분류

• 다이나믹 프로그래밍
• 재귀

 

문제 출처

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

9184번: 신나는 함수 실행

 

---

 

문제 해결 방법

주어진 함수 들여다보기

• 문제의 조건대로 재귀 함수를 작성하면 다음과 같다.

int W(int a, int b, int c) {
    if (a <= 0 || b <= 0 || c <= 0) {
        return 1;    // 종료 조건
    }
    if (a > 20 || b > 20 || c > 20) {
        return W(20, 20, 20);
    }
    else if (a < b && b < c) {
        return W(a, b, c - 1) + W(a, b - 1, c - 1) - W(a, b - 1, c);
    }
    else {
        return 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)을 이용하여 문제를 해결해야 한다.

 

메모이제이션을 위해 필요한 변수 생성하기

• 입력값이 @a@, @b@, @c@ 3개이므로, 다음과 같이 3차원 배열을 선언한다.

int w[][][];

• 다음과 같이 문제에 제시된 함수의 조건문을 보면 재귀 호출이 발생하는 범위는 세 변수가 모두 1 이상 20 이하인 경우로 볼 수 있다. 따라서 1 이상 20 이하가 아닌 수들이 함수의 인자로 들어올 경우, 재귀 함수에 의해 인자가 1이상 20이하인 함수로 호출되어 계산이 진행 된다.

if (a <= 0 || b <= 0 || c <= 0) {
    return 1;    // 종료 조건
}
if (a > 20 || b > 20 || c > 20) {
    return W(20, 20, 20);
}

• 따라서 다음과 같이 배열의 크기를 각각 21로 설정하였다.

int w[21][21][21];

• 이제 나머지 부분은 DP를 이용하여 구현해주면 된다.

 

DP를 이용하여 구현하기

• 메모이제이션한 배열에 값이 들어있을 경우 그 값을 반환시켜주도록 한다.

else if (w[a][b][c]) {     // 배열에 값이 있으면
    return w[a][b][c];
}

• 문제의 나머지 조건대로 배열에 메모이제이션을 해준다.

else if (a < b && b < c) {
    w[a][b][c] = W_DP(a, b, c - 1) + W_DP(a, b - 1, c - 1) - W_DP(a, b - 1, c);
}
else {
    w[a][b][c] = W_DP(a - 1, b, c) + W_DP(a - 1, b - 1, c) + W_DP(a - 1, b, c - 1) - W_DP(a - 1, b - 1, c - 1);
}

• 그리고 위의 모든 조건들을 만족하지 않을 경우, 메모이제이션한 배열에 들어있는 값을 반환하도록 한다.

return w[a][b][c];

 

• 최종적으로 완성한 함수의 코드는 다음과 같다.

int W_DP(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_DP(20, 20, 20);   
    }
    else if (w[a][b][c]) {     // 배열에 값이 있으면
        return w[a][b][c];
    }
    else if (a < b && b < c) {
        w[a][b][c] = W_DP(a, b, c - 1) + W_DP(a, b - 1, c - 1) - W_DP(a, b - 1, c);
    }
    else {
        w[a][b][c] = W_DP(a - 1, b, c) + W_DP(a - 1, b - 1, c) + W_DP(a - 1, b, c - 1) - W_DP(a - 1, b - 1, c - 1);
    }

    return w[a][b][c];
}

 

코드

#include <iostream>
using namespace std;

int a, b, c;
int w[21][21][21];

int W_DP(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_DP(20, 20, 20);    // 20 초과 수는 재귀 함수를 이용하여 범위를 줄여준다.
    }
    else if (w[a][b][c]) {     // 배열에 값이 있으면
        return w[a][b][c];
    }
    else if (a < b && b < c) {
        w[a][b][c] = W_DP(a, b, c - 1) + W_DP(a, b - 1, c - 1) - W_DP(a, b - 1, c);
    }
    else {
        w[a][b][c] = W_DP(a - 1, b, c) + W_DP(a - 1, b - 1, c) + W_DP(a - 1, b, c - 1) - W_DP(a - 1, b - 1, c - 1);
    }

    return w[a][b][c];
}

void Input() {
    cin >> a >> b >> c;
}

void Output() {
    cout << "w(" << a << ", " << b << ", " << c << ") = " << W_DP(a, b, c) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (true) {
        Input();
        if (a == -1 && b == -1 && c == -1) {
            break;
        }
        Output();
    }

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [동적 계획법 1]
• 실버II