백준 1793 - 타일링

문제

https://www.acmicpc.net/problem/1793

1793번: 타일링

 

 

풀이

 

사용할 수 있는 타일이 2 * 1(가로),  2 * 1 (세로), 2 * 2 세 종류이다.

왼쪽부터 차례대록 타일을 채운다고 생각하면서 점화식을 생각해본다.

길이가 i인 타일을 채워야 하고, i-1까지 타일이 채워져 있다면 2 * 1(세로)를 사용하면 된다.

길이가 i인 타일을 채워야 하고, i-2까지 타일이 채워져 있다면 2*1(가로) 두개를 사용하는 방법과 2*2 타일을 사용하는 방법이 있다.

 

따라서 다음과 같은 점화식을 만들 수 있다.

a[i] = a[i-1] + a[i-2] * 2 

 

문제에서 입력으로 가능한 수가 0도 포함되어 있어서 a[0]의 경우도 생각해야 하는데, 2*0의 직사각형은 아무것도 하지 않아도 이미 채워져 있다고 생각을 해서 1로 초기화 해준다. 

 

코드

python

d = [0] * 251
d[0] = 1
d[1] = 1
d[2] = 3
for i in range(3, 251):
    d[i] = d[i - 1] + d[i - 2] * 2
 
while True:
    try:
        n = int(input())
        print(d[n])
    except EOFError:
        break

 

java

import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        BigInteger[] d = new BigInteger[251];
        d[0] = new BigInteger("1");
        d[1] = new BigInteger("1");
        d[2] = new BigInteger("3");
 
        for (int i=3; i<=250; i++) {
            d[i] = d[i-1].add(d[i-2].multiply(new BigInteger("2")));
        }
        
        while (sc.hasNext()) {
            System.out.println(d[sc.nextInt()]);
        }
 
    }
}