[Silver II] 타일링 - 1793

문제 링크

성능 요약

메모리: 15032 KB, 시간: 128 ms

분류

임의 정밀도 / 큰 수 연산, 다이나믹 프로그래밍

제출 일자

2024년 8월 30일 15:47:19

문제 설명

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

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

입력

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

출력

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

풀이 (DP + BigInteger)

먼저 dp 배열의 점화식을 세워야하는 문제이다.

우리가 사용할 수 있는 도형은 2X1 , 2X2 도형 두 가지뿐이다.

고로 위 3개의 도형을 사용해 점화식을 이끌어야 한다.

예를 들어 DP의 i번째를 끝으로 하는 2 x i 벽을 전부 타일로 채우는 경우를 생각해보자.

이때 가능한 경우는 2가지이다.
1. i-1번째 까진 다 채워진 상황에서 남은 한 열을 채워야 하는 경우
2. i-2번째 까지 다 채운 후 남은 두 열을 채워야 하는 경우

상황 1.

이 경우엔 2X1 블럭 하나를 이용해 채우는 방법밖에 없다.

상황 2.

놀랍게도 2X2 블럭이랑 2X1 블럭 사용한거다. 그냥 그렇게 봐주세요.

아무튼 2X2 블럭 하나를 사용하는 경우 1개, 2X1 블럭 2개를 사용하는 경우 1개.
총 2개의 경우의 수가 있다.

i-3의 경우엔 위 i-1과 중복된 상황이 나오므로 우리는 i-1과 i-2의 상황만 가지고 점화식을 세우면 된다.

즉, 식으로 바꾸면 이렇게 된다.

DP[i] = DP[i-1] + DP[i-2]*2;

이와 함께 큰 수를 다루기 위해 BigInteger를 사용할 것이다.

혹여나 BigInteger에 대해 까먹었을 경우
BigInteger에 대해 설명해주신 [블로그]를 링크로 남긴다.

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

public class Main {
	//dp + 큰 수 다루기(BigInteger)
	static BigInteger[] dp = new BigInteger[251];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		calculate(); //dp 배열 값 넣어주기
		
		String input; //입력 없을 때까지 계속 입력받기 위한 용도.
		while((input = br.readLine())!=null) {
			int n = Integer.parseInt(input);
			System.out.println(dp[n]);
		}
	}
	
	public static void calculate() {
		dp[0] = new BigInteger("1"); dp[1]= new BigInteger("1"); dp[2]= new BigInteger("3");
		for(int i=3; i<=250; i++) {
			BigInteger two = new BigInteger("2");
			BigInteger addNum = dp[i-1].add(dp[i-2].multiply(two));
			
			dp[i] = addNum;
		}
	}
}