1309 - 동물원

1. 문제 조건 확인

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

동물원에 사는 사자들을 그림과 같은 우리에 가둔다고 한다. 사자를 가두기 위한 우리에는 배치 문제가 있는데, 사자를 우리에 가로로도 세로로도 붙어 있게 배치가 불가능하다. 여기서 2XN 크기의 우리에서 사자를 배치하는 경우의 수를 구하는 것이 문제이다.

• 입력 조건 

2XN 크기의 우리에서 N값을 입력받는다. N은 10^5이하의 정수이다.

• 출력 조건

2XN 크기의 우리에서 사자를 배치할 수 있는 경우의 수를 출력한다. 그 답은 9901로 나눈 나머지를 출력하여야 한다.

2. 문제 풀이

• 아이디어

문제에서 사자는 가로로 혹은 세로로 붙어 배치하지 못한다고 한다. 즉, 대각선의 배치는 가능하다. 또한 사자를 한마리도 배치하지 않는 것도 가능하다.

즉 한 row에서 사자를 배치하는 방법은 배치하지 않기, 왼쪽에 배치하기, 오른쪽에 배치하기 3가지 방법이 있을 수 있다. 그리고 각 3가지 방법은 직전 row의 배치 방법에 영향을 받는다.(n번째 row는 n-1번째  row의 배치 방법에 따라 영향) n번째 row에 사자를 배치하지 않을 때는 n-1번째 row에서 사자를 배치하지 않은 경우, 왼쪽에 배치한 경우, 오른쪽에 배치한 경우의 모든 경우로부터 가능하다. n번째 row에 사자를 왼쪽에 배치하는 경우는 n-1번째 row에서 사자를 배치하지 않은 경우, 오른쪽에 배치한 경우로부터 가능하다. n번째 row에 오른쪽에 사자를 배치하는 경우는 그 반대가 될 것이다.

이런 생각으로부터 문제를 Dynamic Programming으로 접근할 수 있다. 모든 경우를 전부 확인해야 하며, n번째는 n-1번째의 영향을 받아 계산이 되기 때문이다. 또한 배치 조건이 3가지를 생각했으므로 이에 맞추어 설계한다.

• 코딩

앞서 설명한 것처럼 이문제를 Dynamic Programming으로 접근하기 위해 전역변수로 cage를 선언하였다. cage 배열은 2X3으로 선언했는데, 그 이유는 항상 현재(n)row는 직전(n-1)row의 영향만 받기 때문에, 2개 이상의 row를 생각할 이유가 없기 때문이다. 또한 cage에 배치 가능한 경우가 3가지이므로(배치X, 왼쪽 배치, 오른쪽 배치) 위와 같이 선언하였다. cage 배열의 사용은 아래와 같이 사용하였다.

// cage[n][0] = 이번 칸에 사자를 놓지 않는 경우의 수

// cage[n][1] = 이번 칸에 사자를 왼쪽에 두는 경우의 수

// cage[n][2] = 이번 칸에 사자를 오른쪽에 두는 경우의 수

사용방법을 아이디어와 같이 생각했다면, DP로 문제 해결은 어렵지 않다. cage[n][0](배치X)은 cage[n-1][0](배치X), cage[n-1][1](왼쪽 배치), cage[n-1][2](오른쪽 배치)의 경우의 합과 같을 것이다. cage[n][1](왼쪽 배치)는 cage[n-1][0](배치X),cage[n-1][2](오른쪽 배치)의 영향을 cage[n][2](오른쪽 배치)는 cage[n-1][0](배치X), cage[n-1][1](왼쪽 배치)의 영향을 받는다. 초기의 1번째 row는 모든 경우가 1가지 뿐이므로 1로 초기화 해주었다. 그리고 앞의 과정을 n번 반복해서 모든 경우를 계산하자. 반복과정에 있어 불필요한 메모리를 사용하지 않기 위해서 cage[0]과 cage[1] 두 개의 row만 사용하였다. 이 때, cage[0]는 직전 row, cage[1]은 현재 row를 의미한다.

여기에 더해 우리가 구하는 답은 9901로 나눈 나머지가 된다. 이를 구하기 위해서는 모든 경우에 9901로 나누어주면 된다. 쉽게 생각해서 끝의 경우에서만 나머지로 나누어주는 경우, Overflow가 발생할 수도 있다고 생각해서 정수론의 나머지 연산의 특징을 사용하기로 했다. 나머지 연산에서는 아래의 법칙이 항상 성립한다.

 ( a + m ) % m = a % m

 ( (a % m) + ( b % m) ) % m = ( a + b ) % m 

 ( ( a % m) * ( b % m) ) % m = ( a * b) % m

우리는 문제해결을 위해 덧셈을 시행하고 있으므로, 두번째 줄의 나머지 연산 특징을 사용한다. 즉, a+b를 m으로 나눈 나머지와 a와 b를 나눈 나머지의 합을 다시 m으로 나눈 값이 같다. 이에 기반해서 DP의 모든 단계에서 m으로 나누어주는 경우 동일한 효과를 볼 수 있고, Overflow를 방지할 수 있다.

 

#include<stdio.h>
#include<string.h>
#define DIVISOR 9901
 
int cage[2][3];
// cage[n][0] = 이번 칸에 사자를 놓지 않는 경우의 수
// cage[n][1] = 이번 칸에 사자를 왼쪽에 두는 경우의 수
// cage[n][2] = 이번 칸에 사자를 오른쪽에 두는 경우의 수
 
int main(void) {
    int n;
 
    scanf("%d", &n);
 
    cage[0][0] = cage[0][1] = cage[0][2] = 1;
 
    for (int i = 1;i < n;i++) {
        cage[1][0] = (cage[0][0] + cage[0][1] + cage[0][2]) % DIVISOR;
        cage[1][1] = (cage[0][0] + cage[0][2]) % DIVISOR;
        cage[1][2] = (cage[0][0] + cage[0][1]) % DIVISOR;
        memcpy(cage[0], cage[1], sizeof(cage[1]));
    }
 
    int answer = (cage[0][0] + cage[0][1] + cage[0][2]) % DIVISOR;
    printf("%d", answer);
}

 

• 분류 : Dynamic Programming, Number Theory