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

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

9184번: 신나는 함수 실행

 

 

 

 

---

- 문제

 

  주어진 재귀함수를 그대로 만들면 어마어마한 실행시간이 필요하기에, 실행시간을 줄일 방법을 찾는 문제다.

 

 

---

- 해설

 

메모이제이션이라는 것을 이용하면 된다. 매개변수 값이 (1,1)인 재귀함수에 한 번 접했더라도, 이 값을 저장하지 않으면 다른 경우에 또 (1,1)을 접하면 또 들어오게 된다.

 

하지만, 메모이제이션을 이용하면 (1,1)을 접했을 때 이 값을 저장하게 되어서 다음에 또 접하게 될때 굳이 재귀함수를 이용해서 값을 구할 필요가 없어지기에 실행시간이 어마어마하게 단축된다.

 

 

 

 

---

- 풀이

#include <iostream>
using namespace std;
int store[21][21][21];

// 메모이제이션이 매우 중요했었음, 이거 안하면 아예 50 50 50입력받으면 렉 걸리면서 실행 안될정도로 dfs를 많이함, 메모이제이션!!!!!

int dfs(int a, int b, int c)
{
    if (a <= 0 || b <= 0 || c <= 0)
        return 1;
    else if (a > 20 || b > 20 || c > 20)
        return dfs(20, 20, 20);
    else if (store[a][b][c])
        return store[a][b][c];
    else if (a < b && b < c)
    {
        store[a][b][c] = dfs(a, b, c - 1) + dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);
        return store[a][b][c];
    }
    else
    {
        store[a][b][c] = dfs(a - 1, b, c) + dfs(a - 1, b - 1, c) + dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);
        return store[a][b][c];
    }
}

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

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

    return 0;
}

 

 

---

- 새롭게 알게 된 점

 

메모이제이션 사