반응형

문제 : http://boj.kr/11726
티어 : 실버3
이 문제를 풀기 위해서는 다이나믹 프로그래밍(DP, Dynamic Programming)이라는 기법을 사용하여 문제를 풀어야 한다.
$N$이 $1, 2, 3, ...$일때, 가능한 경우의 수를 직접 구해보면 특정 규칙을 찾을 수 있다.
$A_{i}$를 $N=i$일때 가능한 경우의 수라고 하고,
$(X, Y)$에서 한 패턴안에 가능한 가로블럭의 개수를 $X$, 가능한 세로블럭의 개수를 $Y$라고 하자.
$N=1$일때, $(0, 1)$ 총 1개.
$N=2$일때, $(2, 0), (0, 2)$ 총 2개.
$N=3$일때, $(2, 1), (2, 1), (0, 3)$ 총 3개.
...를 해보면,
$A_{i} = A_{i-1} + A_{i-2}$라는 관계식을 얻어 낼 수 있다.
위 식은 피보나치 수열의 관계식과 같다.
따라서, $O(N)$만에 답을 얻어 낼 수 있다.
dp[1]=1;
dp[2]=2;
int N;
cin >> N;
for(int i=3; i<=N; i++) {
dp[i] = (dp[i-1] + dp[i-2]) % 10007;
}
cout << dp[N] % 10007;반응형
'BOJ' 카테고리의 다른 글
| [BOJ] SASA Programming Contest 2021 Haru_101 ver. (0) | 2022.03.22 |
|---|---|
| [C++] 23827 - 수열(Easy) (0) | 2021.12.17 |
| [C++] BOJ 18108 - 1998년생인 내가 태국에서는 2541년생?! (0) | 2021.09.04 |
| [C++] BOJ 11659 - 구간 합 구하기 4 (0) | 2021.09.04 |
| [C++] BOJ 22236 - 가희와 비행기 (0) | 2021.09.04 |