백준 1309번 동물원 (C++)

문제 링크 : www.acmicpc.net/problem/1309

1309번: 동물원

이 문제에 빠진 설명이 있는데, 한 칸마다 동물은 한 마리씩 배치시킬 수 있다.

 

문제 풀이는 다음과 같다.

1. 한 줄에 사자를 배치시키는 방법은 3가지가 있다.
(1) 아예 배치를 안 시킴 (2) 첫 번째 칸에 배치 (3) 두 번째 칸에 배치

2. 사자는 가로로 세로로 붙어서 배치시킬 수 없다.

가로에 붙어서 배치시킬 수 없다는 말은 각 줄마다 2칸 모두에 사자를 한 마리씩 배치시킬순 없다는 뜻이다. 

세로에 붙어서 배치시킬 수 없다는 말은, 예를 들어 n번째 줄의 첫 번째 칸에 배치시켰을 경우, n-1번째 줄의 첫 번째 칸과 n+1번째 줄의 첫 번째 칸에 배치시킬 수 없음을 뜻한다.

3. 점화식을 3개로 나눈다 

(1) 아예 배치를 안시킬 경우 -> 이 경우 다음 줄에는 (1) 아예 배치를 시키지 않음 (2) 왼쪽에 배치 (3) 오른쪽에 배치가 가능하다

(2) 왼쪽에 배치 시킬 경우 ->이 경우 다음 줄에는 (1) 아예 배치를 시키지 않음 (2) 오른쪽에 배치가 가능하다

(3) 오른쪽에 배치 시킬 경우 -> 이 경우 다음 줄에는 (1) 아예 배치를 시키지 않음 (2) 왼쪽에 배치가 가능하다.

 

#include <iostream>
#define MAX 100000
#define MOD 9901
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int arr[MAX][3] = {0,}, n = 0, ans = 0;
    cin >> n;
    arr[0][0] = 1, arr[0][1] = 1, arr[0][2] = 1;
    for(int i=1; i<n; i++){
        arr[i][0] = (arr[i-1][1]+arr[i-1][2]+arr[i-1][0])%MOD;
        arr[i][1] = (arr[i-1][0]+arr[i-1][2])%MOD;
        arr[i][2] = (arr[i-1][0]+arr[i-1][1])%MOD;
    }
    ans = (arr[n-1][0] + arr[n-1][1] + arr[n-1][2])%MOD;
    cout << ans << "\n";
    return 0;
}

더럽게도 많이 틀렸는데, 9901로 나누는 과정에서 실수를 저질렀다. 혹시 점화식은 맞는 것 같은데 8~9%에서 자꾸 틀렸습니다가 뜰 경우, 아래 코드를 보자. 3가지 수를 모두 더하고 한 번에 나누는 경우랑, 각각을 더하고 동시에 각각을 나누는 경우의 답은 다를 수 밖에 없다.

 

[틀린 코드]

#include <iostream>
#define MAX 100000
#define MOD 9901
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int arr[MAX][3] = {0,}, n = 0, ans = 0;
    cin >> n;
    arr[0][0] = 1, arr[0][1] = 1, arr[0][2] = 1;
    for(int i=1; i<n; i++){
        arr[i][0] = (arr[i-1][1]+arr[i-1][2]+arr[i-1][0])%MOD;
        arr[i][1] = (arr[i-1][0]+arr[i-1][2])%MOD;
        arr[i][2] = (arr[i-1][0]+arr[i-1][1])%MOD;
    }
    for(int i=0; i<3; i++) ans += arr[n-1][i]%MOD;
    cout << ans << "\n";
    return 0;
}