[백준 11726] 2xn 타일링 2 (자바)

백준 11726번 2xn 타일링 2 (자바)

 

 

 

출처

 

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

 

문제

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

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

 

 

입력

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

 

 

 

출력

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

 

 

 

입출력 예

 

 

 

접근 방법

2xn 타일링 문제에서 2x2 타일이 하나 추가된 문제다.

타일이 증가할수록 타일 종류에 맞게 어떻게 증가하는지 찾아야 한다.

 

1. +1 인 경우 2x1 타일 한 개만 추가 가능하다. (아래 표는 모두 2x1 타일이다. 2열은 합치면 1행으로 변해서 그냥 두었다.)

 

2. +2 인 경우 2x1 타일을 두 개 추가할 수 있지만, 한 개 추가한 것과 다른 것이 없으므로 2x1 타일 한 개와 1x2 타일 2개 추가한 경우 2개 경우가 있다.

 

2.1 2x2 타일이 추가로 생겼으므로 (가운데 열은 1x2 타일이다.) 1개의 경우가 추가로 생긴다.

결과적으로 +2인 경우 2x1타일 1개 붙인 경우, 1x2타일 2개 붙인 경우, 2x2타일 1개 붙인 경우 총 3개지가 존재한다. 또한 2배씩 증가할 것이므로 x2를 해주어야 한다.

점화식은 dp[n] = dp[n-1] + 2*dp[n-2] 이다. (하향식 방법)

 

* 하향식 방법이므로 메모이제이션 기법을 사용해 반활할때마다 해당 배열에 값을 넣어준다.

 

* 해당 배열 원소가 0이 아닌 경우 이미 값이 들어간 것이기 때문에 해당 값 그대로 반환해준다.

 

 

 

내 코드

package practice;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class TwoNTiling2 {
	
	private static int[] dp;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(reader.readLine());
		
		dp = new int[n+1];
		
		System.out.println(cycle(n));
		
	}//main

	private static int cycle(int n) {
		
		if (n == 1) {
			return 1;
		}
		
		if (n == 2) {
			return 3;
		}
		
		if (dp[n] != 0) {
			return dp[n];
		}
		
		return dp[n] = (cycle(n-1) + 2*cycle(n-2)) % 10007;
		
	}
}

 

 

 

고려할 점

1. 타일 놓는 규칙을 생각해 점화식을 세울 것

2. 메모이제이션 방식 사용할 것