[백준/C언어] 9184번 - 신나는 함수 실행

백준 웹사이트 "9184번 - 신나는 함수 실행" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

9184번: 신나는 함수 실행

---

소스 코드

#include <stdio.h>

void fill_w();
void w_abc(int a, int b, int c);

//global paramaters
int w[21][21][21];

int main(void){
    fill_w();
    while(1){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        if(a==-1 && b==-1 && c==-1)
            break;

        w_abc(a, b, c);
    }
}

void fill_w(){
    for(int i=0; i<21; i++){
        for(int j=0; j<21; j++){
            for(int k=0; k<21; k++){
                if(i<=0 || j<=0 || k<=0)
                    w[i][j][k] = 1;
                else if(i<j && j<k)
                    w[i][j][k] = w[i][j][k-1] + w[i][j-1][k-1] - w[i][j-1][k];
                else
                    w[i][j][k] = w[i-1][j][k] + w[i-1][j-1][k] + w[i-1][j][k-1] - w[i-1][j-1][k-1];
            }
        }
    }
}

void w_abc(int a, int b, int c){
    if(a<=0 || b<=0 || c<=0)
        printf("w(%d, %d, %d) = %d\n", a, b, c, 1);
    else if(a<=20 && b<=20 && c<=20)
        printf("w(%d, %d, %d) = %d\n", a, b, c, w[a][b][c]);
    else
        printf("w(%d, %d, %d) = %d\n", a, b, c, w[20][20][20]);
}

---

문제 풀이

  문제의 재귀함수 w(a, b, c)를 매번 계산하는 것보다, 가능한 모든 w(a, b, c)를 모두 구해놓은 뒤 필요할 때마다 참고하는 것이 훨씬 좋은 방법입니다. a≤0 or b≤0 or c≤0일 경우 1을 반환, a>20 or b>20 or c>20일 경우 w(20, 20, 20)을 반환하므로, w(0, 0, 0) ~ w(20, 20, 20)의 값들만 구하면 충분합니다.

  소스코드의 fill_w 함수는 w(0, 0, 0) ~ w(20, 20, 20)의 값을 구하는 함수입니다. main 함수의 처음에 한 번만 실행하면 필요한 모든 w[a][b][c] 값이 기록되며, main 함수에서 입력을 받을 때마다 적절한 w[a][b][c] 값을 가져오면 됩니다.