백준] 11727 : 2*n 타일링 (2)

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

11727번: 2×n 타일링 2

 

문제  :

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

입력  : 

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

 

출력  : 

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

 

 

접근 방법

백준 11726 과 유형이 비슷한 문제입니다.

이 문제에서 사용할 블럭은 총 세 개입니다.
1*2 & 2*1 & 2*2입니다.

따라서 
2 X N에서 N이 1일 때는 2*1블록 하나만 필요하므로 총 한 가지의 방법이 있습니다.
N이 2일 때는 2 X 2이므로 총 세 가지의 방법이 존재합니다.

이를 점화식으로 세워보면,

총 길이가 N일 때

길이가 N인 직사각형

N - 1이면 2 * 1블록으로 채우는 한 가지의 방법이 존재하고,

N - 1일 때

N - 2일 때는 두 가지의 방법이 존재함을 알 수 있습니다.

N - 2일 때

첫 번째 방법

두 번째 방법

따라서 점화식은 
dp[n] = dp[ n - 1] + dp[ n - 2 ] * 2로 세울 수 있습니다.

 

 

 

 

 

정답 코드

#include <iostream>
using namespace std;

int dp[10001];

int main() {

	int n;
	
	cin >> n;

	dp[1] = 1; // 2X1일 때, 한 가지 방법만 존재.
	dp[2] = 3; // 2X2일 때, 세 가지 방법만 존재.
	
	for(int i = 3; i <= n; i++){
		dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
	}
	cout << dp[n];

	return 0;
}

 

 

 

 

 

참고한 블로그

21. 다이나믹 프로그래밍 타일링 문제 풀어보기