티스토리 뷰

알고리즘 관련/BOJ

BOJ)9184 신나는 함수 실행

JASON 자손9319 2017. 1. 14. 16:23

문제: icpc.me/9184


문제에서 점화식 기저 까지 다 정해주는 진정한 꿀문제가 아닐까 싶다.


당연하게도 그냥 함수를 매번 계산한다면 시간초과가 난다.


하지만 우리는 점화식과 기저를 알고 있으니 이걸 이용해 다이나믹 프로그래밍을 이용하여 계산할때마다 결과를 배열에 저장해주면 된다.


문제에서 하라는대로 하면 쉽게 풀 수 있는 문제이다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[21][21][21];
int a, b, c;
int func(int x, int y, int z) {
    if (x <= || y <= || z <= 0)
        return 1;
    if (x > 20 || y > 20 || z > 20)
        return func(202020);
    int &ret = dp[x][y][z];
    if (ret != -1)return ret;
    if (x < y&&< z)
        return ret = func(x, y, z - 1+ func(x, y - 1, z - 1- func(x, y - 1, z);
    return ret = func(x - 1, y, z) + func(x - 1, y - 1, z) + func(x - 1, y, z - 1- func(x - 1, y - 1, z - 1);
}
int main() {
    memset(dp, -1sizeof(dp));
    scanf("%d%d%d"&a, &b, &c);
    while (!(a == -&& b == -&& c == -1)) {
        printf("w(%d, %d, %d) = %d\n", a, b, c, func(a, b, c));
        scanf("%d%d%d"&a, &b, &c);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5480 전함  (0) 2017.01.14
BOJ)10167 금광  (0) 2017.01.14
BOJ)9184 신나는 함수 실행  (0) 2017.01.14
BOJ)1049 기타줄  (0) 2017.01.14
BOJ)2022 사다리  (2) 2017.01.14
BOJ)2252 줄 세우기  (0) 2017.01.14
댓글
댓글쓰기 폼