JArchive 프로그래밍 일기

문제

동물원 백준 1309번

리뷰

처음에는 왼쪽에 사자를 놓냐, 오른쪽에 놓냐만 생각하다가 점화식을 세우지 못했다.

구글링을 해보니까 [ 안 놓는다. 왼쪽칸에 놓는다. 오른쪽 칸에 놓는다. ] 세 가지로 생각한 포스팅이 있었고, 그제서야 이해가 됬다.

사자를 배치 안하는 것도 경우로 친다는 것을 유념해야하는 문제였다.

D[ N ] [ L ] 배열을 D[ 행 ] [ 열 ] 에 사자를 배치하는 경우의 수를 저장한다.

N = 1 일 때, 동물 우리는 1 * 2 칸이다.

1행 2칸이니까 사자를 배치하는 경우의 수는 [ 아예 안 놓는다. 왼쪽칸에 놓는다. 오른쪽 칸에 놓는다 ] 이렇게 3가지다.

따라서 D[1] [0] = 1 , D[1] [1] = 1 , D[1] [2] = 1

이것이 기본 값이다 (base case)

N = 2 일 때, 동물 우리는 2 * 2 칸이다.

D[2] [0] 에는 2행에 사자를 배치 안하는 경우다. 이 경우에는 1행에 사자를 배치 하든 말든 상관이 없다.

따라서 D[2] [0] = D[1] [0] + D[1] [1] + D[1] [2] = 3가지

D[2] [1] 에는 2행의 왼쪽칸에 사자를 배치하는 경우다. 이 때는 1행에 사자를 배치안하거나 1행 오른칸에 배치해야 한다.

따라서 D[2] [1] = D[1] [0] + D[1] [2] = 2가지

D[2] [2] 에는 2행의 오른쪽 칸에 사자를 배치하는 경우다. 이 때는 1행에 사자를 배치안하거나 1행 왼쪽칸에 배치해야 한다.

따라서 D[2] [2] = D[1] [0] + D[1] [1] = 2가지

그래서 아래의 점화식으로 정리할 수 있다. 값을 저장하기 전에 9901로 mod 연산을 해줘야 한다.

for(i = 2; i <= ca_size ; i++) { // 행 순회  
    D[i][0] = (D[i-1][0] + D[i-1][1] + D[i-1][2]) % MODNUM; 
    D[i][1] = (D[i-1][0] + D[i-1][2]) % MODNUM; 
    D[i][2] = (D[i-1][0] + D[i-1][1]) % MODNUM;  
}    

뭐지 .. 하면서 아리까리 했었고 혼자힘으로는 못했는데.

어렵지만 풀면서 재미있었다. 

다른 분들의 풀이를 검색해보니까, 더 간단한 점화식 풀이가 있었다.

N에 따라 경우의 수를 써보다가 규칙을 발견하셨나보다.

N   ans
1   3
2   7
3   17
4   41
dp[n] = dp[n-1]*2 + dp[n-2]

코드

#include <stdio.h>
#include <algorithm>
#define MODNUM 9901
using namespace std;

int D[100001][3];

int main(void){

    freopen("input.txt", "rt", stdin);

     int ca_size = 0;
     int i = 0 ;

    scanf("%d", &ca_size);     

    // 0 사자 없음, 1 왼쪽칸에 배치, 2오른쪽칸에 배치. 

    D[1][0] = D[1][1] = D[1][2] = 1;  //     1 행의 경우,  

    for(i = 2; i <= ca_size ; i++) { // 행 순회  
        D[i][0] = (D[i-1][0] + D[i-1][1] + D[i-1][2]) % MODNUM; 
        D[i][1] = (D[i-1][0] + D[i-1][2]) % MODNUM; 
        D[i][2] = (D[i-1][0] + D[i-1][1]) % MODNUM;  
    }    

     printf("%d", (D[ca_size][0] + D[ca_size][1] + D[ca_size][2]) % MODNUM);

    return 0;
}