백준 1309번 동물원

🔒[문제 url]

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

🪄전체 코드

#include <iostream>
using namespace std;

#define MOD 9901
int n;
int dp[100'001];

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
}


void SOLVE()
{
    dp[0] = 1; dp[1] = 3;

    for(int i = 2; i <= n; i++)
    {
        // dp[i] = dp[i - 1] + 2 * dp[i - 2] + 1 * (dp[i - 1] - dp[i - 2]) 변형
        /*
        dp[i - 1]의 경우에서, 한 줄이 추가되는 경우이다.
        추가된 줄에 배치하지 않는 경우 : dp[i - 1]
        추가된 줄의 왼쪽과 오른쪽 모두에 배치할 수 있는 경우 : 2 * dp[i - 2]
        추가된 줄에서 선택지가 한 곳밖에 없는 경우 : 1 * (dp[i - 1] - dp[i - 2])
        */
        dp[i] = (2 * dp[i - 1]) % MOD + dp[i - 2] % MOD;
        dp[i] %= MOD;
    }

    cout << dp[n];
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.