1309.동물원

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

<입력>

우리의 크기 N(1<=N<=100,000)

<출력>

사자를 배치하는 경우의 수를 9901로 나눈 나머지

<풀이>

2xN 타일링과 같은 전형적인 dp문제이다.

이런 방식의 문제는 부분 문제로 나누어 점화식을 세워야 한다.

사자는 가로 세로로 인접할 수 없다.

즉, 세로 3번 칸에 있는 사자는 4번 칸에는 영향을 주지만 5번 칸에는 주지 못한다.

N-2 칸을 채우는 방법은 N번째 칸에 어떤 값이 들어오던지 영향을 받지 않는다.

따라서 N번째 칸을 왼쪽에 사자를 놨을 때 / 오른쪽에 사자를 놨을 때 / 놓지 않았을 때로 나누어

a(N-2) * 3이 우선적으로 포함됨을 알 수 있다.

다음으로 N-1 칸을 채우는 방법을 생각해야 한다.

우선 N-2칸을 이미 모두 고려했기 때문에 a(N-1) - a(N-2)를 해준다.

(이 때, 9901로 나눈 나머지이므로 a(N-1)이 더 작아질 수 있으므로 예외처리 해줘야 한다.)

그럼 전과 마찬가지로 N-1번째 칸의 왼쪽이 차있을 경우 / 오른쪽이 차있을 경우로 나누었을 때

N번째 칸이 N-1번째 칸의 반대쪽에 있거나 / 비어있거나 2가지 경우가 존재하므로

(a(N-1) - a(N-2)) * 2이 마지막으로 포함된다.

따라서 위와 같은 점화식이 만들어진다.

이를 풀어서 a(N-1)*2 + a(N-2)로 만들 경우 a(N-1)이 a(N-2)보다 커지는 경우를 예외처리할 필요가 없어진다.

이 방법을 통해 9901로 나누는 경우를 더 쉽게 구할 수도 있다.

---

- 소스 코드 -

#include<iostream>
 
using namespace std;
 
typedef long long ll;
 
int main(void){
    ll arr[100001]={0};
    arr[0]=3;
    arr[1]=7;
    int N;
    cin>>N;
    for(int i=2;i<=N;i++){
        if(arr[i-1]<=arr[i-2]){
            arr[i]=0LL+((arr[i-2]*3)+((arr[i-1]+9901-arr[i-2])*2))%9901;  
        }else{
            arr[i]=0LL+((arr[i-2]*3)+((arr[i-1]-arr[i-2])*2))%9901;  
        }
        
    }
    cout<<arr[N-1]<<endl;
}
 

---