[C++] (백준 11726 번) 2×n 타일링

 

문제출처: 백준
문제 링크: https://www.acmicpc.net/problem/11726
난이도: ★★☆☆☆

• 문제 분류: 다이나믹 프로그래밍 (dp)

[문제]

 

---

[분석]

base case는 n=1 or n=2일 경우이다.

 

(i) n=1                                        (ii) n=2                     

recursive case는 n>=3일 경우이다.

 

n=3일 때를 예로 들자면,

n=1일 때 만들어진 도형에 타일을 두개 붙이는 경우와 n=2일 때 만들어진 도형에 타일을 한개 붙이는 경우가 존재한다.

(i) n=1 일 때 만들어진 도형에 타일을 두개 붙이는 경우

(i) n=2 일 때 만들어진 도형에 타일을 한개 붙이는 경우

이렇게 나누어진다.

오른쪽 위아래가 사실상 같은 경우가 되므로 1+2=3이다.

따라서 2X(N-1)도 역시 점화식에 의해 2X(N-2)에 타일을 하나 붙여서 만든 것이기 때문에 같은 경우에 해당한다.

일반화하면 2xN=2x(N-1)+2x(N-2) -> cnt[n]=cnt[n-1]+cnt[n-2] 이다.

 

 

따라서 점화식은 다음과 같이 구성가능하다.

• 점화식

 

문제에서는 10007을 나눈 나머지를 출력하라고 하며, 배열에 저장할 때도 표현 범위보다 커지기 때문에 오버플로우가 발생하여 10007을 나눈 나머지를 배열에 저장하게 된다. * 나머지를 배열에 저장하지 않고 원래 값을 저장하면 답이 틀리다.

• 10007을 나눈 나머지를 저장하는 것이 점화식에 영향을 미치지 않는 이유는 무엇일까?

약간 이런 방식을 따라가는 듯 함.

---

[코드]

#include <iostream>
using namespace std;


unsigned long long cnt[1001];
int main() {
	cnt[1]=1;cnt[2]=2;
	int n;
	scanf("%d",&n);
	for(int i=3;i<=n;i++) cnt[i]=(cnt[i-1]+cnt[i-2])%10007;
    cout<<cnt[n]<<endl;
	return 0;
}

1부터 채워주는 방식으로 했기 때문에 배열의 크기를 1001로 하였다.