[JAVA] 백준 1793번 타일링

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

1793번: 타일링

백준 문제 링크입니다.

문제 난이도는 solved.ac에 실버 2 난이도로 되어 있습니다.

 

이 문제는 DP로 푸는 문제이고,

타일 유형입니다.

수가 매우 커지기 때문에 BigInteger를 활용했습니다.

---

문제는 2XN 직사각형을 2X1과 2X2 타일로 채우는 방법의 수를 구하는 문제입니다.

2X1 타일을 회전해서 1X2 타일로 만들 수 있습니다.

N의 범위는 0 <= N <= 250 입니다.

 

[사진 1] 타일

사진 1의 타일들을 배치해서 2XN 직사각형을 채워야 합니다.

 

입력 값은 N을 계속 입력 받습니다.

출력 값은 입력 받은 N의 2XN 직사각형을 채우는 방법의 수를 출력합니다.

 

배열 dp의 크기를 N의 최대 범위인 250을 담기 위하여 251로 초기화 해줍니다.

이때 dp값이 매우 커질 수 있기 때문에 자료형은 BigInteger로 합니다.

BigInteger[] dp = new BigInteger[251];

 

모든 dp 값을 저장해주고, 입력 값을 받아 한번에 출력시키는 방법을 사용했습니다.

 

2XN 직사각형을 N이 0일때부터 확인하겠습니다.

 

N : 0, 2X0

 

N이 0일때는 채울 타일이 없습니다. 즉, 아무 타일을 사용하지 않는 방법 1가지가 있습니다.

dp[0] = 1;

 

N : 1, 2X1

 

2X1 직사각형을 채우는 방법은 세로로 길쭉한 2X1 타일을 사용하는 방법 1가지가 있습니다.

dp[1] = 1;

 

N : 2, 2X2

 

[사진 2] 2X2 채우는 방법

2X2 직사각형을 채우는 방법은 3가지입니다.

dp[2] = 3;

 

N : 3, 2X3

 

[사진 3] 2X3 채우는 방법

사진 3에서 숫자의 의미는 가로의 길이입니다.

1은 2X1을 의미하고, 2는 2X2를 의미합니다.

 

사진 3의 방법을 좀 더 자세히 채워보겠습니다.

 

[사진 4] 2X3 채우는 과정

사진 4의 방법 외에 2X3 직사각형을 채우는 방법은 없습니다.

위 방법을 보면 2X1 타일과 사진 2의 2X2 직사각형으로 채우는 모습을 볼 수 있습니다.

즉,

① 2X2 직사각형을 먼저 쓰고 2X1 타일을 사용하는 방법과

② 2X1 타일을 먼저 쓰고 2X2 직사각형을 사용하는 방법이 있습니다.

 

②를 하는 방법을 구하면,

2X1 타일을 만드는 방법의 수 * 2X2 직사각형을 만드는 방법의 수를 구하면, ②의 총 개수입니다.

이때, 2X2 직사각형을 만드는 방법은 dp[2] = 3으로 먼저 구했습니다.

 

근데, 사진 4에서 보면 알 수 있듯이 중복되는 과정들이 있습니다.

2X1 타일만 쓰는 방법에서 중복이 나타났습니다.

즉, ①의 2X2 직사각형을 만들 때 2X1 타일만 쓰는 방법을 제외해야 합니다.

①의 2X2 직사각형 만드는 방법의 수 * 2X1 타일을 만드는 방법의 수를 구하면, ①의 총 개수입니다.

 

dp[3] = 5; //dp[1] * dp[2] + 2 * dp[1]

 

N : 4, 2X4

 

마지막으로 4까지 확인하겠습니다.

 

[사진 5] 2X4 채우는 방법

① 2X1 타일을 먼저 쓰고 2X3 직사각형을 사용하는 방법

② 2X2 직사각형을 먼저 쓰고 2X2 직사각형을 사용하는 방법

③ 2X3 직사각형을 먼저 쓰고 2X1 직사각형을 사용하는 방법이 있습니다.

 

사진 5의 과정을 자세히 보겠습니다.

 

[사진 6] ① 채우는 과정

①를 하는 방법을 구하면,

2X1 타일을 만드는 방법의 수 * 2X3 직사각형을 만드는 방법의 수를 구하면, ①의 총 개수입니다.

이때, 2X3 직사각형을 만드는 방법은 dp[3] = 5으로 먼저 구했습니다.

 

[사진 7] ② 채우는 과정

②를 하는 방법을 구하면,

2X2 직사각형을 만드는 방법의 수 * 2X2 직사각형을 만드는 방법의 수를 구하면, ②의 총 개수입니다.

이때도 중복이 있습니다.

사진 7을 잘 보면 앞의 2X2 직사각형을 만드는 과정 중에 2X1 타일만 쓰는 과정들(첫번째 열)이 중복됩니다.

즉, 앞의 2X2 직사각형이 2X1 타일을 쓰지 않는다면 중복되지 않습니다. - 2가지

②의 총 개수 = 앞의 2X2 직사각형 방법의 수(2) * 나머지 직사각형(dp[2] = 3) = 6

 

[사진 8] ③ 채우는 과정

③ 을 채우는 과정은 모두 중복되기 때문에 더해주지 않습니다.

 

dp[4] = ① + ② = dp[1] * dp[3] + 2 * dp[2] = 11

 

이 문제는 ① + ②만 해주면 해결되는 문제입니다.

 

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

dp[i] = dp[i - 1] + 2 * dp[i - 2]; //dp[1] = 1이기 때문에 생략합니다.

 

[사진 9] 코드

테스트 해볼 때 주의점은 입력값을 계속 받다가 null 값이 들어오면 입력이 끝나는 방식입니다.

그래서 입력 값이 null일 때, 종료하도록 했습니다.

이 코드는 백준에서는 정답으로 인정되지만, 이클립스에서 오류가 나니 테스트 해보고 싶다면 while문 안에서 하나씩 출력해보시면 됩니다.

 

[사진 10] 정답 확인

---

제가 공부한 부분을 정리한 내용이기 때문에 틀린 부분 있을 수 있습니다!!

혹시 틀린 부분이 있으면 알려주세요!!