[백준] 9184번 : 신나는 함수 실행

문제

 

---

풀이

 

3차원 배열을 써야겠다! 라는 생각을 했다면 빨리 해결했을 것이고...

나처럼 거의 쓸 일 없는 3차원 배열을 대충 기억속에서 지우고 살았던 사람이라면 좀 걸렸을지도 모르겠다.

 

난 시간초과에 대한 강박이 있는데 그래서 이 문제에 재귀함수 호출을 전혀 쓰지 않았다.

조건을 보니 아무리 for문이 많이 돌아도 최대 20*20*20 = 8000번이길래 3중 for루프를 사용했다.

근데 다른 사람들의 풀이를 보니 거의 다 재귀를 사용하셨던데 뭐 이런 풀이도 있다는 걸 보는 정도로 봐주길...

---

소스코드

 

#include <iostream>

using namespace std;

int w_func(int a, int b, int c) { //재귀를 약간 써도 시간초과가 생기지는 않는가 보다...
    int w[21][21][21] = {0};

    if (a <= 0 || b <= 0 || c <= 0)
        return 1;
    if (a > 20 || b > 20 || c > 20) {
        a = 20;
        b = 20;
        c = 20;
    }
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            for (int k = 0; k <= c; 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];
            }
        }
    }
    return w[a][b][c];
}

int main() {
    int a, b, c;

    while (true) {
        cin >> a >> b >> c;
        if (a == -1 && b == -1 && c == -1)
            break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w_func(a, b, c) << '\n';
    }
}

대충 w(0, 0, 0)부터 w(a, b, c)까지 값을 채운 것이다.