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

1. 문제이해

11726번: 2×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

 

주어진 n에 대해 2×n 크기의 직사각형을

1×2, 2×1 타일로 채우는 방법의 수를 구하는 것이 목표이다.

단, 방법의 수를 10,007로 나눈 값을 출력해야 한다.

 

 

 

2. 문제풀이

 

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

아래 그림을 통해 n이 1일때부터 하나씩 증가해가며 타일을 채우는 방법을 알아보자.

 

위 그림을 통해,

n번째 타일을 채우는 경우의 수 = (n - 1)번째 경우의 수 + (n - 2)번째 경우의 수

임을 확인할 수 있다.

이렇듯, 도출해낸 풀이방법을 통해 구현한 코드는 아래와 같았다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int main() {
	int n;
	int Rectangle[1000];

	cin >> n;

	Rectangle[0] = 0;
	Rectangle[1] = 1;
	Rectangle[2] = 2;

	// n번째 타일을 채우는 경우의 수 
	// = (n - 1)번째 경우의 수 + (n - 2)번째 경우의 수
	for (int i = 3; i <= n; i++) {
		Rectangle[i] = (Rectangle[i - 1] + Rectangle[i - 2]) % 10007;
	}

	cout << Rectangle[n];

	return 0;
}

배열 Rectangle을 선언하고, n을 입력받는다.

Rectangle[i]는 2×i 번째 직사각형을 1×2, 2×1 타일로 채우는 방법의 수이다.

 

Rectangle[0], Rectangle[1], Rectangle[2] 값을 미리 선언해 준 뒤,

2. 문제풀이에서 구한

n번째 타일을 채우는 경우의 수 = (n - 1)번째 경우의 수 + (n - 2)번째 경우의 수를 적용해준다.

( Rectangle[i] = (Rectangle[i - 1] + Rectangle[i - 2]) % 10007; )

문제에서 해당 값을 10007로 나눈 나머지를 출력하라고 했으므로, %10007을 해주었다.

 

 

---

막상 그림을 그려 풀어보니, 다이나믹 프로그래밍 문제였다.

언제풀어도 DP문제는 헷갈리는 것 같다.. 식 도출해내는 과정도 비교적 어려운것 같기도 하고..🤔

설명은 글로만 설명하면 역시 눈에 안들어올 것 같아서 급하게 삼성노트에 적어보았는데,

아이패드의 필요성을 또 한번 절실하게 느꼈다..🤣

조만간 아이패드를 하나 장만해야지... 꼭...😭😭