[C++] 백준/Silver/1309. 동물원

문제: 동물원(백준 1309번)

문제 분석

3칸짜리 우리에 사자를 배치하는 문제로, 각 줄에 사자를 배치하는 경우의 수를 구하는 DP 문제다.
조건: 같은 줄에 사자를 가로로 붙어있게 배치할 수 없다.

점화식 도출:

• dp[i] = i번째 줄까지 사자를 배치하는 경우의 수
• 세 가지 경우의 수:
  1. 사자를 배치하지 않는 경우
  2. 왼쪽 칸에 사자를 배치하는 경우
  3. 오른쪽 칸에 사자를 배치하는 경우

이 조건을 고려하면 점화식은 다음과 같다.

$dp[i]=(dp[i−1]×2)+dp[i−2]dp[i] = (dp[i-1] \times 2) + dp[i-2]$

• dp[i-1] × 2: 이전 줄에서의 모든 배치 경우에 대해, 이번 줄에 왼쪽 또는 오른쪽에 사자를 추가하는 경우
• dp[i-2]: 두 줄 전의 배치에 이번 줄을 빈 상태로 두는 경우 (붙어있을 수 없기 때문)

초기값

• dp[0] = 1: 아무 줄이 없을 때의 경우의 수 (공집합)
• dp[1] = 3: 한 줄일 때의 경우의 수 (왼쪽 배치, 오른쪽 배치, 배치하지 않음)

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> dp(n + 1);
    dp[0] = 1, dp[1] = 3;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] * 2 + dp[i - 2];
        dp[i] %= 9901;
    }
    cout << dp[n];
}