#1309 동물원

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

1309번: 동물원

실버 1의 문제이다. 문제는 복잡하지 않았고 내 생각이 짧다는것을 다시 느꼈다.

#include <iostream>
#include <algorithm>
#define mod 9901
using namespace std;

long long dp[100001][3];

int main()
{
  //freopen("input.txt","r",stdin);
  int n;
  int ans=0;
  cin>>n;
  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][1]+dp[i-1][2])%mod;
    dp[i][1]=(dp[i-1][0]+dp[i-1][2])%mod;
    dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%mod;
  }

  for(int i=0;i<3;i++){
    ans+=dp[n][i];
  }

  cout<<ans%mod;
}

내가 먼저 생각했던것에 대해서 써보겠다. 나는 일단 처음에 2차원 배열 dp[][]를 사용하여 점화식을 쓰고자 했다.

dp[N자리][사자 수] 로 표현하고자 했고, N번째 줄을 채웠을때, 채우지 않았을때를 나누어 점화식으로 쓰려고 했었다. 그러다보니 N번째 자리를 채웠을때, 채우지 않았을때 이렇게 두가지 경우가 필요했고 3차원배열을 썼다. 

dp[N자리][사자 수][마지막줄을 채우는지]  따라서, dp[2][1][1] 은 2x2 크기의 동물원에 한마리의 사자를 채우되 2번째 줄에 사자를 넣는다. 이런식으로 하려고했다.

그런데 마지막 줄에 동물을 채우면 N-1번째 줄에 동물을 채울 수 없는 칸이 생기고, 이게 반복 되다보면 굉장히 복잡해짐을 느꼈다. 내 생각이 짧다고 느꼈던게, 각 줄에 들어갈 수 있는 경우의 수는 X X / X O / O X 이렇게 세가지가 있고, 이를 활용하면 되는데 나는 한칸씩 따지고자 했다. 한 줄 씩 따졌으면 여태 풀었던 dp문제와 흡사해서 금방 풀 수 있었을텐데 ㅠ...

 

아무튼 한 줄에 동물을 넣을 수 있는 경우는 X X / X O / O X 이고 각 경우를 2,1,0 으로 사용한다. 2차원 배열을 사용한다. dp[N개줄][마지막줄의 상태].

N번째 줄에 X X의 상태 즉 2라면, N-1번째에는 X X / X O / O X 모두가 가능하기 때문에 점화식은 다음과 같다.

dp[N][2] = dp[N-1][0]+dp[N-1][1]+dp[N-1][2];

N번째 줄에 X O의 상태 즉 1이라면, N-1번째에는 O X / X X 가 가능 하고 이를 점화식으로 표현하면,

dp[N][1] = dp[N-1][0]+dp[N-1][2]; 이다

N번째 줄에 O X의 상태 즉 0이라면, N-1번째에는 X O / X X 가 가능하고 이를 점화식으로 표현하면,

dp[N][0] = dp[N-1][1]+dp[N-1][2]; 이다.

 

이를 코드로 구현하면 끝이다.