[Algorithm] Baekjoon 1309번 : 동물원

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

1309번: 동물원

int dp[100001][3];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    cin >> n;
    
    dp[1][0] = 1; // 1번째줄에 아예 배치 X.
    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]) % 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;
    }
 
    cout << (dp[n][0] + dp[n][1] + dp[n][2]) % 9901;
}

solved.ac의 class4문제는 거의 다 풀어서 이제는 더 레벨높은 문제를 풀기보다는 다시 기본을 튼튼히 하려한다.

문제푸는데 걸리는 시간이 생각보다 꽤 긴 편이다.

 

어쨌든 이번문제는 오랜만의 DP문제이다.

이 문제는 DP배열을 2차원으로 해서 해결한다.

2차원으로 할 경우 각 행마다 3개의 열을 가지게 하는데 해당 행에 사자를 배치 안하거나, 왼쪽에 배치하거나, 오른쪽에 배치하거나 하는 경우이다.

 

i번째 행에 배치를 안할 경우 그 전 행에 사자를 어떻게 배치하든(왼쪽이든,오른쪽이든,배치를 안했든) 상관없기 때문에 해당 값들을 전부 더해준다. (즉, 전 행의 모든 경우의수를 더해준다.)

 

i번째 행의 왼쪽에 배치를 할 경우, 그 전 행의 0번째 열값(배치를 안했을 경우값)과 2번째 열의 값(오른쪽에 배치를 할 경우)를 더해준다. (배치하려면 그 전행에 배치된 사자의 대각선으로만 배치할 수 있으니까)

 

i번째 행의 오른쪽도 왼쪽처럼 배치해주면 된다.

 

그리고 문제에 주어진 값으로 %연산해주는것을 절대 잊으면 안되고, 출력하기 직전에도 한번 해줘야한다.

 

사실 풀이들을 보면 1차원으로도 하는 문제가 있긴하다.

그런데 '왜' 그렇게 됐다기보다는 규칙을 우연히 발견해서 푼 케이스라... 나도 한번 이해해보려했는데 잘 안되서 일단은 넘어간다. 어쨌든 O(n)인건 동일하니까