풀이
d1[i] = 2*i인 우리에서 i번째 칸에 사자를 0마리 놓는 경우의 수
d2[i] = 2*i인 우리에서 i번째 칸의 한 쪽에만 사자를 1마리 놓는 경우의 수
d1[i] = d1[i-1] + d2[i-1] * 2
d2[i] = d1[i-1] + d2[i-1]
위의 식을 그대로 써도 좋지만, 1차원으로 더 압축해보자!
위에서 정의한 d1과 d2를 잘 기억하자.
d1[i] = d1[i-1] + d2[i-1] * 2
d1[i] = (d1[i-2] + d2[i-2] * 2) + (d1[i-2] + d2[i-2]) * 2
d1[i] = (d1[i-2] * 3) + (d2[i-2] * 4) = (d1[i-1] * 2) + d2[i-1] (d1과 d2의 정의에 의해)
d1[i] = d1[i-1] * 2 + d1[i-2]
끝!
코드
#include <stdio.h>
int main() {
int n, d[100001] = { 1,3 };
scanf("%d", &n);
for (int i = 2; i <= n; i++)
d[i] = (d[i - 1] * 2 + d[i - 2]) % 9901;
printf("%d", d[n]);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이