백준 1793번 타일링 : JAVA

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

 

먼저 가능한 도형을 보자면 다음과 같습니다.

 

(1) 2x1에서 가능한 도형

 

(2) 2x2에서 가능한 도형

 

(3) 2x3에서 가능한 도형 - 추론

3-1

- (2)의 모양에서 오른쪽에 2x1 타일 (1)을 추가하였습니다.

- (2)의 모양에서 왼쪽에 2x1 타일 (1)을 추가하였습니다.

- 이는 (1) 모양에서 오른쪽에 2x1 타일 (1)을 추가한 것과 같습니다. (아래 사진)

3-2

- 추가적으로 마지막 도형은 3-1의 마지막 도형과 같으므로 계산되지 않습니다. 

 

그렇다면 여기서 합리적인 추론을 해볼 수 있습니다.

3-1의 모양은 (2)의 모양에서

을 추가한 것과 같으니 (기존의 모양 수) * 1 이 되었다고 볼 수 있습니다.

이는 (i - 1 번 모양의 수) * 1 으로 계산됩니다.

 

3-2의 모양은 (1)의 모양에서 

을 각각 추가한 것과 같으니 (기존의 모양 수) * 2 이 되었다고 볼 수 있습니다.

이는 여유공간이 2칸 필요하므로 2번째 이전 모양에 추가한것이라 볼 수 있습니다.

즉, (i - 2 번 모양의 수) * 2 으로 계산됩니다.

모양은 1번 계산에서 항상 계산되므로 계산에 포함되지 않습니다.

 

(3)의 최종 모양은 아래와 같습니다.

 

(4) 2x4에서 가능한 도형

그렇다면 위에서 세운 추론식을 적용해볼까요?

먼저 1번 계산. 

i - 1 번째 (3번째) 모양에 위 도형을 추가해줍니다.

 

2번 계산.

i - 2 번째 (2번째) 모양에 위 도형을 추가해줍니다.

 

총 11가지의 모양이 나오게 되며, 직접 도형을 만들어봐도 위와 같은 도형이 나오게 됩니다.

 

그렇다면 이 추론식을 이용해 다음과 같은 점화식을 세울 수 있습니다.

 

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

 

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        List<Integer> list = new ArrayList<>();

        String input = "";
        // 백준 제출용
        while ((input = br.readLine()) != null) {
        // 인텔리제이용
//        while ((input = br.readLine()) != null & !input.isEmpty()) {
            list.add(Integer.parseInt(input));
        }

        BigInteger[] DP = new BigInteger[250 + 1];

        //기본값 설정
        DP[0] = new BigInteger("1");
        DP[1] = new BigInteger("1");
        DP[2] = new BigInteger("3");

        //테스트케이스가 여러개 들어오므로 미리 모든값을 계산해놓음
        for (int i = 3; i <= 250; i++) {
            DP[i] = DP[i - 1].add(DP[i - 2].multiply(new BigInteger("2")));
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (Integer num : list) {
            bw.append(DP[num].toString()).append("\n");
        }

        bw.flush();
        bw.close();
    }
}