[BOJ] 백준 1793번 타일링 (Java)

#1793 타일링

난이도 : 실버 1

유형 : DP

9466번: 텀 프로젝트

▸ 문제

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이

동빈나님 유튜브를 보면서 배웠던 알고리즘이라 점화식은 쉽게 찾아내었다. long보다 더 큰 수를 출력하여야해서 java.math의 BigInteger를 사용했다.

 

📚 조건

   ∙ 숫자 n (0 <= n <= 250)

 

타일이 들어갈 수 있는 방법이 몇 개인지 차근차근 구해주면 된다. 새로운 타일이 들어갈 수 있는 종류는 아래 3개이다.

타일 종류

 

1) dp[n-1]에서 길이 1을 추가하게 되는 경우 1x2 타일이 들어오는 방법 1가지밖에 없다.

 

2) dp[n-2]에서 길이 2을 추가하게 되는 경우 2x1 타일 2장과 2x2 타일 1장 들어오는 방법 총 2가지이다.

 

3) dp[n-3]부터는 n-1, n-2의 방법과 중복이기 때문에 count를 해주지 않아도 된다.

 

 

그래서 점화식은 다음과 같다.

☛ dp[n] = dp[n-1] + 2*dp[n-2];

 

풀이 코드

BigInteger함수를 사용했다. 다소 int를 ""로 감싸고 변수를 넣어줄 수 없다는 게 별로 좋아보이진 않았지만 그래도 잘 출력되었다.

import java.io.*;
import java.math.BigInteger;

public class Main {

	static BigInteger[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
		dp = new BigInteger[251];
		
		dp[0] =new BigInteger("1");
		dp[1] =new BigInteger("1");
		dp[2] =new BigInteger("3");
		
		for(int i=3; i<251; i++) {
			dp[i] = dp[i-1].add(dp[i-2].multiply(new BigInteger("2")));
		}

		String line = null;
		while((line=br.readLine())!=null) {
			int n = Integer.parseInt(line);
			System.out.println(dp[n]);
		}
		br.close();
	}
}

 

+

 

그리고 정해진 입력 종료조건이 없어서 Scanner를 사용해야할지 잠시 망설였었다.

while(sc.hasNextInt()) { // 입력이 존재하면 계속 반복한다. , 테스트 케이스가 존재하지 않기 때문
	int n=sc.nextInt(); // n이 들어오면
	System.out.println(dp[n]); // 해당 n값을 출력한다.
}

 

좀 찾아본 결과 BufferdReader에도 방법이 있었다.

String line = null;
while((line=br.readLine())!=null) {
	int n = Integer.parseInt(line);
	System.out.println(dp[n]);
}
br.close();