[백준 / C언어] 1309번: 동물원 (dp)

https://www.acmicpc.net/problem/1309

1309번: 동물원

 

난이도: solved.ac 실버 1

 

 

알고리즘 분류

---

다이나믹 프로그래밍 (dp)

 

접근 방법

---

이 문제에서 중요한 부분은 가로 또는 세로로 붙여서 배치시킬 수 없다는 것이다

따라서, 사자를 배치하는 경우는 아래 세 가지로 나눌 수 있다

1) 이전 칸에서 왼쪽에 배치한 경우

2) 이전 칸에서 오른쪽에 배치한 경우

3) 이전 칸 둘 다 배치하지 않은 경우

 

1번의 경우에는 이전에 왼쪽에 배치되어 있으므로 왼쪽에 또 배치시킬 수 없다

따라서 오른쪽 칸에 배치시키거나 아예 둘 다 비워놓는 경우만 가능하다

 

2번의 경우에는 이전에 오른쪽에 배치되어 있으므로 오른쪽에 또 배치시킬 수 없다

따라서 왼쪽에 배치시키거나 아예 둘 다 비워놓는 경우만 가능하다

 

3번의 경우에는 이전의 두 칸 모두 비어있으므로 어느 쪽에나 배치시킬 수 있다

따라서 왼쪽에 배치시키는 경우, 오른쪽에 배치시키는 경우, 두 칸 모두 비워놓는 경우 세 가지가 가능하다

 

이를 그림으로 나타내면 아래와 같다

 

이를 점화식으로 나타내면 다음과 같다

 

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
int main() {
	int N;
	scanf("%d", &N);
	int pL, pR, pO, sum;
	int L = 1, R = 1, O = 1;
	while (--N) {
		pL = L;
		pR = R;
		pO = O;
		L = (pR + pO) % 9901;
		R = (pL + pO) % 9901;
		O = (pL + pR + pO) % 9901;
	}
	sum = (L + R + O) % 9901;
	printf("%d", sum);
	return 0;
}