[BOJ] 백준 #1309. 동물원 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/1309

• 알고리즘 분류: 다이나믹 프로그래밍
• 난이도: Silver 1

 

 

💬 풀이

처음에는 수학 조합문제 느낌으로 생각하다가, 노가다로 직접 N=1, N=2, N=3, ...일때 구하다가 DP 문제라고 삘이 왔다.

 

사실 내가 푼 방법은 N=1부터 N=4까지 노가다로 직접 값을 구한 뒤에, 그냥 끼워맞춰서 점화식을 구했다.

한마디로 야매로 풀었다는 것,,,ㅎㅎ

즉, 직접 dp[1]=3, dp[2]=7, dp[3]=17, dp[4]=41까지 구해놓은 다음에, 3,7,17,41,...에서 이전 항을 이용해서 숫자를 어떻게 하면 나올지 껴맞춰 보다가 일반화된 식 dp[n] = 2*dp[n-1] + dp[n-2]를 구할 수 있었다.

 

너무 운빨로 문제가 풀려버려서 위 점화식에 대한 풀이를 찾아봤고, 그 내용은 다음과 같다.

 

우선 한 줄에 배치할 수 있는 경우는 (X,X), (🦁,X), (X,🦁) 이렇게 총 3가지다.

이제 dp[n] : n번째 줄까지 사자를 배치하는 총 경우의 수 를 구해보자

1. 이때 만약 n번째 줄에 사자를 배치하지 않는다면, dp[n-1]가지다.
2. 또 만약 n번째 줄 왼쪽에 사자를 배치한다면, (n-1)번째 줄에 사자를 오른쪽에 배치하거나 아예 안 할 수 있다.
3. 또 만약 n번째 줄 오른쪽에 사자를 배치한다면, (n-1)번째 줄에 사자를 왼쪽에 배치하거나 아예 안 할 수 있다.
4. 위 2,3 경우를 합치면, (n-1)번째 줄까지만 배치하는 경우에다가 (n-1)번째에는 아예 안 하는 dp[n-2]를 더한 수다. 즉, dp[n-1]+dp[n-2]

다 더하면 내가 야매로 구한 점화식 dp[n] = 2*dp[n-1] + dp[n-2]가 나온다.

 

 

 

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX 100001
#define MOD 9901
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	//freopen("input.txt", "rt", stdin);
	int N;
	cin >> N;
	int dp[MAX];
	dp[1] = 3; dp[2] = 7;
	for (int i = 3; i <= N; i++) {
		dp[i] = (2 * dp[i - 1] + dp[i - 2]) % MOD;
	}
	cout << dp[N];

	return 0;
}

 

 

 

많은 참고 Thank you~🙇‍♀️

https://guiyum.tistory.com/21

https://hongjw1938.tistory.com/66