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

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

11726번: 2×n 타일링

 

어떤 문제인가?

2*n크기의 직사각형을 1*2, 2*1의 타일로 채우는 방법의 수를 구하는 것이다.

간단한 dp문제이다.

 

 

접근 방법

n이 1일 때

2*1 타일만을 사용해 한 가지 방법밖에 없다.

 

n이 2일 때

2*1 타일 두 개를 사용하는 방법

1*2 타일 두 개를 사용하는 방법

두 가지 방법

 

n이 3일 때 세 가지 방법

n이 4일 때 다섯 가지 방법

 

규칙이 보이는가? n이 3 이상일 때

dp[ n ] = dp [ n -1 ] + dp [ n - 2]의 규칙성을 갖게 된다.

 

int dp[1001];

n이 1000까지 입력될 수 있으니 그에 맞게 dp배열을 선언해준다.

 

 

dp[1] = 1;
dp[2] = 2;

규칙성이 시작되기 전인 첫 번째, 두 번째 경우는 알고 있으므로 각각 맞게 초기화해준다.

 

 

int n;
cin >> n;

n을 선언하고 입력받는다.

 

 

for (int i = 3; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;;
}

3부터 n까지 반복문을 통해 dp값을 계산해준다.

이때 문제의 조건대로 10007로 나눈 나머지를 계산해준다.

 

cout << dp[n];

n번째 dp값을 출력해주면 끝!!

 

 

무엇이 어려웠는가?

원래는 마지막 출력 부분에 dp[n] % 10007으로 해주었더니 '틀렸습니다.'가 떴다.

문제를 다시 이해하니 각각의 dp값을 10007로 나눈 나머지를 저장해야 하는 것이었다.

 

점화식은 패드에 그림을 그리다가 쉽게 찾을 수 있었다.