코드 복사/붙여넣기 하는 당신이 아름답습니다.

1309 : 동물원

풀이

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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-08-05 23:11

Read more posts by this author