이 문제는 동적계획법으로 푸는 문제로

시간초과는  memoization으로 해결하면 되고

딱히 큰 어려움은 없는 문제이다.



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
27
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[36];
 
unsigned long long t(int n) {
    if (n == 0)
        return result[n] = 1;
    if (result[n] > 0)
        return result[n];
    else {
        for (int i = 0; i < n + 1; i++)
            result[n] += t(i)*t(n - i - 1);
        return result[n];
    }
}
 
int main() {
    int input;
    cin >> input;
    cout << t(input);
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13

이 문제는 동적계획법으로

첫 번째 타일이 세로로 있을 때(n-1)랑 2개의 타일이 가로로 되어있을 때(n-2)의 경우의 수를 합하는 것과 같다.

이는 피보나치 수열과 같으므로 같은 방법으로 풀면 된다.



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
27
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[1001];
 
unsigned long long fibonacci(int n) {
    if (n == 1)
        return result[n] = 1;
    if (n == 2)
        return result[n] = 2;
    if (result[n] > 0)
        return result[n];
    else
        return result[n] = (fibonacci(n - 1) + fibonacci(n - 2))%10007;
}
 
int main() {
    int input;
    cin >> input;
    cout << fibonacci(input);
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17

이 문제는 간단한 동적 계획법을 이용하여 풀 수 있다.

어떤 동적계획법이든 마찬가지지만 시간초과가 제일 문제이다.

일단 이 문제는 확률과통계에서 나오는 조합을 이용하여 풀 수 있다.

eCr = e-1Cw-1 + e-1Cw (e = east, w = west) 공식을 이용하여 풀면 된다.

eC0 = 1일 때와 e==w일 때를 출구조건으로 하면 간단하게 풀 수 있다.

(memoization을 이용하지 않으면 시간초과가 뜨므로 주의한다.)



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
27
28
29
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[30][30];
 
unsigned long long combination(int east, int west) {
    if (east == west || west == 0)
        return result[east][west] = 1;
    if (result[east][west] > 0)
        return result[east][west];
    else
        return result[east][west] = combination(east - 1, west - 1) + combination(east - 1, west);
}
 
int main() {
    int N;
    int west, east;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> west >> east;
        cout << combination(east, west) << endl;
    }
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17
[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03

+ Recent posts

티스토리툴바