백준 1309 동물원 쉬운 풀이(C++/CPP)

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

문제 접근

• 어떻게 해야하는지 감이 안오는데? 우선 각 케이스를 구해보자
  • 2 X 0 : 0마리 1
  • 2 X 1 : 0마리 1, 1마리 2
  • 2 X 2 : 0마리 1, 1마리 4, 2마리 2
  • 2 X 3 : 0마리 1, 1마리 6, 2마리 8, 3마리 2
• 다음 우리의 개수와 이전 우리의 개수의 연관관계 찾을때, 사자가 인접하지 않는다는 조건 때문에 복잡
  • 첫째줄에 사자가 없는경우, 왼쪽에 있는경우, 오른쪽에 있는 경우로 나누면 어떨까 >> 케이스별 2차원 DP
  • DP[N][0] = 2XN 타일 중 첫번쨰 줄에 사자 없는경우 = DP[N-1][0] + DP[N-1][1] + DP[N-1][2]
  • DP[N][1] =2XN 타일 중 첫번쨰 줄의 왼쪽에 사자 있는경우 = DP[N-1][0] + DP[N-1][2]
  • DP[N][2] =2XN 타일 중 첫번쨰 줄의 오른쪽에 사자 있는경우 = DP[N-1][0] + DP[N-1][1]
• 초기조건
  • DP[0][0] = 1, DP[0][1] = 0, DP[0][2]= 0
  • DP[1][0] = DP[0][0] + DP[0][1] + DP[0][2] = 1
  • DP[1][1] = DP[0][0] + DP[0][2] = 1
  • DP[1][2] = DP[0][0] + DP[0][1] = 1
• 사자가 없는 경우의수는 DP[0][0] 에 포함되며, 이후에도 계속 포함되서 계산됨

시간복잡도 계산

• N칸에서 3번 계산 해줘야함, O(3*N), 3e5

인트 계산

• 경우의수 9901 나머지 이므로 인트 범위 가능

코드

#include <iostream>
 
using namespace std;
 
int dp[100010][3];
int main() {
    int N; cin >> N;
    fill(&dp[0][0], &dp[100009][3], 0);
    
    dp[0][0] = 1;
    for(int j=1; j<=N; j++) {
        dp[j][0] = (dp[j-1][0] + dp[j-1][1] + dp[j-1][2]) %9901;
        dp[j][1] = (dp[j-1][0] + dp[j-1][2]) %9901;
        dp[j][2] = (dp[j-1][0] + dp[j-1][1]) %9901;
    }
    
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) %9901 << '\n';
    
    return 0;
}
 

문제유형

• 케이스별 2차원 DP
  • 각 케이스로 쪼개서 DP를 계산
  • 조건이 조금 복잡하다 싶으면, 이 유형인지 한번 확인 필요

비슷한 문제

• https://www.acmicpc.net/problem/2579