[Baekjoon/Silver 3/Java] 11726번: 2×n 타일링

Baekjoon(백준) 11726번: 2×n 타일링

11726번: 2×n 타일링

문제 설명

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

풀이

처음 생각한 풀이는 N을 1 또는 2로 이루어진 조합으로 만드는 형태로 접근을 했었는데,
(예: 4 -> 1+1+1+1 / 2+1+1 / 1+2+1 / 1+1+2 / 2+2)
수가 커질 수록 수행 시간도 빠르게 증가할 것 같다는 생각이 들어 다른 풀이를 생각해야 했다.

한참을 고민하다가 결국 다른 사람의 풀이를 보았는데, 타일의 조합에서 다음과 같은 규칙이 있다는 것을 알게 되었다.

가로 길이가 K인 경우, K-2의 타일 조합 오른쪽에 타일이 2개가 붙어 만들어진 방법과 K-1의 타일 조합 오른쪽에 타일이 1개가 붙어 만들어진 방법으로 이루어져 있다.

가로 길이가 K인 경우의 타일 조합의 수를 d[k]라 하면,
결국 d[k] = d[k-2] + d[k-1]이 성립이 된다는 것이다. 이는 피보나치 수열과 동일하다.

 

Java로 구현한 코드는 다음과 같다. DP로 구현해 보았다.
다만, 구현의 편의를 위해 0번째는 0개여야 하지만, 1로 지정하였다.
제약 조건에서 N이 0인 경우는 없으므로 채첨이 틀리지는 않는다.

import java.util.*;

class Solution {
	int solution(int n) {
		int answer = 0;
		int[] cntWays = new int[n + 1];
		
		cntWays[0] = 1; // 계산의 편의를 위해 0번째를 1로 지
		cntWays[1] = 1;
		
		for (int i = 2; i <= n; i++) {
			// 각 경우를 연산할 때마다 10007의 나머지로 저장해야 한다
			cntWays[i] = (cntWays[i - 2] + cntWays[i - 1]) % 10007;
		}
		answer = cntWays[n];
		return answer;
	}
}

public class test2798 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Solution solutionEntity = new Solution();
		int input = scanner.nextInt();
		System.out.println(solutionEntity.solution(input));
	}
}

 

* 참고한 풀이

[알고리즘] 백준 11726번, 2xn 타일링 JAVA풀이