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

 

9184번: 신나는 함수 실행

 

문제!

---

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

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

 

---

위와 같이 재귀를 돌려주면 되는 문제!

 

그냥 재귀를 돌리려고 했으나 좀더 줄일 수 있을것 같아서 방법을 찾아 보았습니다.

 

1. 0이하와 20 이상의 수들은 생각 해주지 않아도 된다! 

>>> 조건에서 재귀로 처리해주었기에 0~20 까지의 배열만 만들어도 될것 같네요!

 

2. 입력 받을때마다가 아닌 구해놓고 저장해놓은뒤 불러오는 메모이제이션 방식으로!

>> 이 부분은 쉽게 가능 할것 같아요!

 

 

그럼 1번부터 시작!

 

미리 20* 20* 20 배열을 만들고 그 안에서 한번 돌려줍시다.

int table[21][21][21] = {0};  

void cal() {
    for (int a = 0; a <= 20; a++) {
        for (int b = 0; b <= 20; b++) {
            for (int c = 0; c <= 20; c++) {
                if (a == 0 || b == 0 || c == 0) {
                    table[a][b][c] = 1;
                }
                else if (a < b && b < c) {
                    table[a][b][c] = table[a][b][c - 1] + table[a][b - 1][c - 1] - table[a][b - 1][c];
                }
                else {
                    table[a][b][c] = table[a - 1][b][c] + table[a - 1][b - 1][c] + table[a - 1][b][c - 1] - table[a - 1][b - 1][c - 1];
                }
            }
        }
    }
}

 

그다음부터 입력을 받는데

여기서 cin>> num1>>num2 >> num3 ; 를 이용해서 받으니까 속도가.... 엄청 느려지네요 >> 이건 나중에 찾아보고!

 

 

그래서 scanf 를 사용해서 받고 조건들으 통과 시켜 줍시다.

while (1) {
        scanf("%d %d %d", &num1, &num2, &num3);

        if (num1 == -1 && num2 == -1 && num3 == -1) {
            break;
        }
        else if (num1 <= 0 || num2 <= 0 || num3 <= 0) {
            printf("w(%d, %d, %d) = %d\n", num1, num2, num3, 1);
        }
        else if (num1 > 20 || num2 > 20 || num3 > 20) { // 여기서 테이블 크기 구분가능
            printf("w(%d, %d, %d) = %d \n", num1, num2, num3, table[20][20][20]);
        }
        else {
            printf("w(%d, %d, %d) = %d \n", num1, num2, num3, table[num1][num2][num3]);
        }
    }

 

(답 출력에서 \n 으로 한줄씩 띄워줘야해요 이거 몰라서 한참걸렸네요....)

 

그러면 끝!

 

 

 

 

ALL

#include <iostream>

using namespace std;

int num1, num2, num3;
int answer;

int table[21][21][21] = {0};  

void cal() {
    for (int a = 0; a <= 20; a++) {
        for (int b = 0; b <= 20; b++) {
            for (int c = 0; c <= 20; c++) {
                if (a == 0 || b == 0 || c == 0) {
                    table[a][b][c] = 1;
                }
                else if (a < b && b < c) {
                    table[a][b][c] = table[a][b][c - 1] + table[a][b - 1][c - 1] - table[a][b - 1][c];
                }
                else {
                    table[a][b][c] = table[a - 1][b][c] + table[a - 1][b - 1][c] + table[a - 1][b][c - 1] - table[a - 1][b - 1][c - 1];
                }
            }
        }
    }
}

int main() {
    
    cal();

    while (1) {
        scanf("%d %d %d", &num1, &num2, &num3);

        if (num1 == -1 && num2 == -1 && num3 == -1) {
            break;
        }
        else if (num1 <= 0 || num2 <= 0 || num3 <= 0) {
            printf("w(%d, %d, %d) = %d\n", num1, num2, num3, 1);
        }
        else if (num1 > 20 || num2 > 20 || num3 > 20) { // 여기서 테이블 크기 구분가능
            printf("w(%d, %d, %d) = %d \n", num1, num2, num3, table[20][20][20]);
        }
        else {
            printf("w(%d, %d, %d) = %d \n", num1, num2, num3, table[num1][num2][num3]);
        }
    }
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!