백준, BOJ, 1309번, 동물원 : C++ [CPP]

 

처음에 감을 못잡았는데..

N-1번째에 사자를 놓느냐 마느냐를 집중했어야 했는데

사자가 1마리 일때, 사자가 2마리 일때, 사자가 3마리 일때의 규칙을 찾으려니까 못찾았다.

 

나의 실수다.

 

시간제한을 보니 2초다.

또한 최소 100,000개의 배치를 해야한다.

배열로 만들지 고민했다.

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

 

 

---

 

#맞는 풀이

#include <iostream>

using namespace std;

int N;
const int MAX = 100001;

int dp[MAX][3]; //120만 바이트 -> 1.2메가정도

int main(){
    cin >> N;
    
    dp[1][0] = 1; //1번째 줄에 아무것도 놓지 않는 경우
    dp[1][1] = 1; //1번째 줄에 왼쪽에 사자를 놓는 경우
    dp[1][2] = 1; //1번째 줄에 사자를 오른쪽에 놓는 경우
    
    for(int i = 2; i<=N; i++){
        dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]; //이전에 아무렇게 놔도 된다.
        dp[i][1] = dp[i-1][0] + dp[i-1][2]; //같은 쪽에 놔두면 안됨
        dp[i][2] = dp[i-1][0] + dp[i-1][1]; //""
        
        //9901로 나눈 값만 저장하면 됨
        dp[i][0] %= 9901;
        dp[i][1] %= 9901;
        dp[i][2] %= 9901;
    }
    
    cout << (dp[N][0] + dp[N][1] + dp[N][2])%9901;
    
}

 

 

N-1에 사자를 두느냐 마느냐를 정했어야 했다.

사자 몇마리냐가 중요한 것이 아니었따.