11726 2xN 타일링

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

11726번: 2×n 타일링

 

문제를 보자마자 막막했다. 경우의 수가 많을 것 같다는 생각이 들었는데 패턴이 있는지 궁금했다.

 

일단 작은 길이부터 개수를 계산했다. 

N = 2)

1x2, 2x1 두 개다.

 

N = 3)

첫 두 개를 돌리거나 뒤에 있는 두 개를 돌리거나 안돌리는 방법까지 총 3개다.

 

N = 4)

다 더해보면 5개다.

 

N = 5)

다 더해보면 8개다. 

 

개수를 세어보니 피보나치 수열과 똑같았다. 설마 답이 그건가 싶어 제출했더니 통과했다.

#include <iostream>
int dp[1001]{1,1,0};
int f(int n){
    if(dp[n]){
        return dp[n];
    }
    dp[n] = (f(n-1) + f(n-2))%10007;
    return dp[n];
}
int main(){
    int N;
    scanf("%d", &N);
    printf("%d", f(N));
}

---

통과했으면 됐다고 생각해 다른 문제를 풀러 갔지만 비슷한 문제를 만나 골치아픈 상황이 생겼었다.

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

2302번: 극장 좌석

 

그 문제를 제대로 해결하고 어쩌다 이 문제를 보았는데 똑같은 내용이어서 정리해야겠다고 마음먹었다.

 

문제의 답이 피보나치인 이유는 이렇다.

 

타일은 돌리거나 돌리지 않기, 두 가지 선택이 가능하다.

편의상 돌린다는 표현은 2x1 타일로 채울 때를 의미한다고 생각해달라.

 

1. 만약 제일 앞 한 개를 돌리지 않았다면, 그 한 개를 제외한 나머지 타일들의 조합이 곧 답에 포함된다. 

 

2. 만약 제일 앞 한 개를 돌렸다면, 돌리는 데 한 개의 타일이 더 필요하므로 그 두 개의 타일을 제외한 나머지 타일들의 조합이 곧 답에 포함된다.

N이 4라고 가정하면 1번같은 경우는 나머지 3개의 타일들의 조합이 답에 포함된다.

 

2번 같은 경우는나머지 2개의 타일들의 조합이 답에 포함된다.

 

아까 타일은 돌리거나 돌리지 않는다는 선택만 가능하다 했으므로 위 두 개의 조합들을 더하면 N이 4일 때의 답이 나온다.

 

그럼 N=3일 때도, N=2일 때도 위의 공식이 적용된다. 물론 N이 1이거나 0이면 1가지 밖에 안된다.

 

따라서 F가 모든 경우의 수를 구하는 함수라고 하면 다음의 식이 곧 답이 된다.

 

F(N) = F(N-1) + F(N-2) 

F(N-1)은 돌리지 않았을 때 나머지 타일들의 조합의 수다.

F(N-2)는 돌렸을 때 나머지 타일들의 조합의 수다.