백준 1309번 동물원 [C++]

#문제 간단 정리

dp 를 사용해서 풀어야한다

 

#문제 해결 방법

문제 상황

먼저, 문제 상황을 이해해야 합니다. 여기서는 가로로 2칸, 세로로 N칸인 우리가 있고, 사자들을 배치하는 문제입니다. 조건은 다음과 같습니다:

• 사자들은 가로나 세로로 붙어 있을 수 없습니다.
• 사자를 한 마리도 배치하지 않는 경우도 포함합니다.

동적 프로그래밍 이해하기

DP는 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 이 문제에서는 'N번째 칸까지 사자를 어떻게 배치할 수 있는가'를 작은 문제로 삼습니다. 각 칸에 대해 다음과 같은 세 가지 경우를 생각해볼 수 있습니다:

1. 사자를 배치하지 않는 경우.
2. 사자를 첫 번째 칸에만 배치하는 경우.
3. 사자를 두 번째 칸에만 배치하는 경우.

DP 배열 설정

DP를 사용하기 위해 각 상태를 저장할 배열을 설정합니다. dp[N][3] 배열을 사용하며, 여기서 N은 우리의 크기를 나타내고, 두 번째 차원의 크기 3은 위의 세 가지 경우를 나타냅니다.

초기 조건 설정

DP 배열의 초기값을 설정합니다. 첫 번째 칸에 대해 사자를 배치하지 않거나, 첫 번째 칸이나 두 번째 칸 중 하나에만 배치하는 경우는 각각 1가지 방법이 있습니다. 따라서 dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 1로 초기화합니다.

점화식 구성

다음으로, 각 단계에서의 값들을 계산하는 규칙, 즉 점화식을 구성합니다. N번째 칸에 대해 생각해보면:

• 사자를 배치하지 않는 경우 (dp[N][0]): 이전 칸(N-1)에 사자가 어디에 배치되었든 상관없으므로 dp[N-1][0], dp[N-1][1], dp[N-1][2]의 합입니다.
• 사자를 첫 번째 칸에만 배치하는 경우 (dp[N][1]): 이전 칸에 사자가 첫 번째 칸이나 배치되지 않았어야 하므로 dp[N-1][0]과 dp[N-1][2]의 합입니다.
• 사자를 두 번째 칸에만 배치하는 경우 (dp[N][2]): 이전 칸에 사자가 두 번째 칸이나 배치되지 않았어야 하므로 dp[N-1][0]과 dp[N-1][1]의 합입니다.

결과 계산

모든 칸에 대해 계산을 마치고 나면, 최종적으로 N번째 칸에 대해 세 가지 경우의 수를 모두 더하면 됩니다. 이 때, 문제에서 주어진 대로 9901로 나눈 나머지를 취합니다.

코드 구현

위의 단계들을 코드로 구현하면, 초기화 부분과 점화식을 반복문으로 계산하는 부분, 그리고 최종 결과를 출력하는 부분으로 나누어집니다.

#전체 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<vector<int>> dp (N+1, vector<int> (3,0));
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;

    for (int i = 2; i <= N; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
    }

    int result = (dp[N][0] + dp[N][1] + dp[N][2]) % 9901;

    cout << result <<'\n';

    return 0;
}