[Java] [백준 1793][DP] 타일링

문제

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 

출력

입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다.

 

---

 

🌈 풀이 후기

• DP문제를 많이 풀어보지 않아서 점화식을 세우는데 시간이 좀 걸렸습니다. 재귀적으로 생각해서 풀었습니다.
• 사실 이 문제는 자바로 풀어서 화가나는 문제... 파이썬은 그냥 되는데 자바는 꼭 범위가 크면 문제더라고요.. BigInteger를 사용해야 해서 자바로 풀기 좀 귀찮은 문제였습니다.
• 여기에 찾아야 하는 개수도 안정해져서 귀찮음 *2..
• 그래도 틀리길래 찾아보니 0일때 1이더라고요 ㅎㅎ.... 0인 경우는 당연히 없다고 생각해서 2번 틀렸습니다..ㅠ

👩‍🏫 문제 풀이

알고리즘 - DP

 

-가로 길이가 0 , 1 , 2일때는 각각 경우가 1, 1, 3입니다. 이 경우는 미리 초기에 정해줍니다. 가로 길이가 0 인 경우는 아무것도 만들 수 없다는 뜻으로 0이 아닌 1의 경우의 수를 갖습니다..(주의)

 

-가로길이가 3인 경우부터 점화식을 세우면 Dp[i] = dp[i-1] + dp[i-2]*2 입니다. 점화식이 이렇게 나오는 이유는 다음 예시를 통해 확인해보겠습니다.

 

ex) 가로 길이가 4인 경우

1. 가로 길이가 3인 경우에서 세로 타일을 추가한 경우 ⇒ dp[i-1]
2. 가로 길이가 2인 경우에서 2*2 정사각형 타일을 추가한 경우 ⇒ dp[i-2]
3. 가로 길이가 2인 경우에서 가로 타일을 추가한 경우 ⇒ dp[i-2]

를 재귀적으로 생각할 수 있습니다.

 

이때, 가로 길이가 2인 경우에서 세로 타일을 추가하는 경우는 1번과 동일하기에 제외시켜줍니다.

 

즉 dp[i]는 dp[i-1]인 경우의 수 + dp[i-2] *2인 경우의 수 입니다.

 

이렇게 까지 파이썬으로는 구할 수 있는데 자바로는 범위가 너무 커서 답을 구할 수 없습니다.

 

자바에서는 BigInteger라는게 있는데 이게 범위는 아마 무제한?으로 알고 있습니다. 대신 쓰는 규칙이 좀 특이해서 사칙 연산을 하려면 그냥 하면 안되고 .add , .multiply 처럼 사용해야 합니다...

 

package com.Boj.seoul8.week5;

import java.math.BigInteger;
import java.util.Scanner;

// DP
// 자바 범위 초과...
public class BOJ_S1_1793_타일링 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		BigInteger[] dp = new BigInteger[251];

		dp[0] = new BigInteger("1");
		dp[1] = new BigInteger("1");
		dp[2] = new BigInteger("3");

		// dp[i-1]에서 세로 한줄 + dp[i-2]에서 2*2 정사각형 경우와 가로로 자른경우 2가지
		for (int i = 3; i <= 250; i++)
			dp[i] = dp[i - 1].add(dp[i - 2].multiply(new BigInteger("2")));

		while (sc.hasNextInt()) {
			System.out.println(dp[sc.nextInt()]);
		}

	}

}