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

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

 

 

 

출처

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

 

문제

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

입출력 예

 

 

접근 방법

처음 접해보는 DP 문제다.

규칙을 찾아 점화식을 세우는 것이 중요한 알고리즘이다.

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

 

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

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

결과적으로 점화식은 dp[n] = dp[n-1] + dp[n-2] 이다. (하향식 방법)

 

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

 

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

 

 

 

내 코드

package practice;

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

public class TwoNTiling {
	
	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 2;
		}
		
		if (dp[n] != 0) {
			return dp[n];
		}
		
		return dp[n] = (cycle(n-1) + cycle(n-2)) % 10007;
	}//cycle
}

 

 

 

고려할 점

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

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