백준 1309번 동물원

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

1309번: 동물원

풀이

다이내믹 프로그래밍 문제입니다!

2X1 칸에 사자를 배치하는 경우는

• 왼쪽 사자
• 오른쪽 사자
• 사자 없음

세 가지이며, 사자들은 가로,세로에 붙어있을 수 없다. 

각각의 경우를 0,1,2로 표현했을 경우

d[i][j] = i칸에 j상태의 사자가 있을 경우 사자 배치의 경우의 수

라고 표현 가능하며 각각

• d[i][0] = d[i-1][1] + d[i-1][2]
• d[i][1] = d[i-1][0] + d[i-1][2]
• d[i][2] = d[i-1][0] + d[i-1][1] + d[i-1][2]

이다. 따라서 정답은 d[i]에 해당하는 원소들을 모두 더해준 값을 9901로 나누면 된다.

참고로 n의 최댓값이 100,000 이므로 경우의 수를 구할 때 마다 9901로 나누어 주어야 long long 범위 내에 출력이 가능합니다!

 

소스 코드

#define mod 9901
#include <iostream>
using namespace std;
 
long long d[100001][3];
int main()
{
    int n; scanf("%d", &n);
    d[1][0] = 1; d[1][1] = 1; d[1][2] = 1;
    for (int i = 2; i <= n; i++) {
        d[i][0] = (d[i - 1][0] + d[i - 1][1] + d[i - 1][2]) % mod;
        d[i][1] = (d[i - 1][0] + d[i - 1][2]) % mod;
        d[i][2] = (d[i - 1][0] + d[i - 1][1]) % mod;
    }
    long long ans = 0;
    for (int i = 0; i < 3; i++) {
        ans = (ans + d[n][i]) % mod;
    }
    printf("%lld", ans);
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~