[백준(BOJ)/C++] 11726번: 2xn 타일링 - 코딩밥상

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

11726번: 2×n 타일링

 

 

• 접근 방법, 논리 흐름(알고리즘)

문제를 보고 일단 빈 종이에 n값이 변할 때의 경우들을 그려보았다.

여기서 찾을 수 있는 규칙은 n이 1씩 증가하는데, n이 3이상일 때

2가지의 경우만 고려하면 된다.

1. n이 증가하면서 끝자리에 2x1의 막대가 추가되는 경우(세로 막대)

2. n이 증가하면서 끝의 두자리에 2x2의 막대가 추가되는경우 (가로막대 2층)

 

첫번째의 경우는 그 전 단계에 끝에 세로막대만 추가하면 되기때문에 n-1 단계의 경우의 수 그대로 나온다.

두번째의 경우는 끝에 두자리를 먼저 채우고 나머지의 칸을 채우는 경우이기 때문에 n-2 단계의 경우의 수 그대로 나온다.

즉 x(n) = x(n-1) + x(n-2)라는 점화식을 세울 수 있기때문에 다이나믹프로그래밍을 적용하여 문제를 풀 수 있는것이다.

 

 

• 풀이 코드

이 때 문제에서 나온것과 같이 오버플로우를 피하기 위해 10007을 모듈연산 해준다.