[백준 11726번] 2 x n 타일링

[백준 11726번] 2 x n 타일링

[프로그래머스] 2 x n 타일링

C++ 풀이

​

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

---

복습을 위해 먼저 어제 공부했던 완전탐색법으로 풀었다. 당연 시간초과였다.

int cal(int leftWidth, int leftCount, int sum) {
	if (leftCount == 0)
		return sum;
	else if (leftCount == 1) 
		return sum + (leftWidth - 1);
	else {
		for (int i = 2; i <= leftWidth - 2; i++)
			sum = cal(leftWidth - i, leftCount - 1, sum);
		return sum;
	}	
}

int solution(int n) {
	int answer = 0;
	for (int i = 1; i <= n / 2; i++) {
		answer = answer + cal(n, i, 0);
	}
	return (answer + 1) % 1000000007; //타일을 가로로 배치하지 않는 경우 포함
}

 

두 번째 시도는 규칙을 찾아서 풀기였다.

​

크기 1부터 차례대로 구해보면

n = 1 -> 1개 (1)

n = 2 -> 2개 (1 + 1)

n = 3 -> 3개 (1 + 2)

n = 4 -> 5개 (1 + 3 + 1)

n = 5 -> 8개 (1 + 4 + 3)

n = 6 -> 13개 (1 + 5 + 6 + 1)

.

.

.

​

규칙을 발견할 수 있다.

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

각 n일때의 개수는 n-1과 n-2일때 개수의 합과 같다.

​

다시 코드 작성

int solution(int n) {
	int answer = 0;
	int p = 1;
	int q = 1;
	if (n == 1)
		return 1;
	else {
		for (int i = 2; i <= n; i++) {
			answer = (p + q) % 1000000007;
			p = q;
			q = answer;
		}
	}
	return answer % 1000000007;
}

 

고쳤는데도 계속 타임 에러가 뜨길래 질문글을 보니 answer를 구할때마다 % 1000000007 를 해주어야 수가 커지지 않아 에러가 나지 않는다고 하였다. 그래서 수정하였더니 다행히 맞았다.

참고로 백준에서는 % 10007, 프로그래머스에서는 % 1000000007 가 문제에 나와있다.

​

​

​문제 링크↓

https://programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링 | 프로그래머스

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

11726번: 2×n 타일링