2133번: 타일 채우기

2133번: 타일 채우기

 

타일 채우기 

 

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 

2

예제 출력 1 

3

 

---

풀이

타일링 문제는 이전에 풀었던 경험이 있다.

바로 이 문제이다.

1793번: 타일링

 

위의 타일링 문제에서 좀 더 진화된 문제가 이번 문제로,

3*n 크기를 2*1, 1*2 크기의 타일로 채워야 한다.

3*n이니 2*n 문제를 풀때보다 예외를 좀 더 생각하며 문제를 풀어야 한다.

---

설계

 

n의 홀수, 짝수 판단

 

2*n 크기의 문제는 n이 홀수이든, 짝수이든 상관이 없었다. 2*1, 1*2 크기의 타일로 모든 벽을 채울 수 있었기 때문이다.

 

하지만, 3*n 문제는 n이 짝수일 때만 2*1, 1*2 크기의 타일로 벽을 채울 수 있다. 

n일 홀수라면 1*1 크기의 공간이 항상 남기 때문이다.

 

일단 n이 짝수일 때만 타일 채우기가 가능하다는 건 알았다.

 

어떻게 타일을 채울 것인가? 

 

일단 n이 2일때부터 경우의 수를 확인해보자. 

 

1️⃣ n=2

 

3*2의 크기를 채우는 경우의 수는 모두 3가지이다.

dp[2] = 3

 

 

2️⃣ n=3

 

홀수니까 X

 

3️⃣ n=4

 

3*4의 크기를 채우는 경우의 수는 모두 11가지이다.

 

주황색으로 색칠한 오른쪽을 보면 n=2일때의 3개의 경우의 수가 나오는 것을 확인할 수 있다.

총 n=2일때의 경우의 수가 3번씩 나오므로 dp[4] = dp[2]*3 이라고 할 수 있다.

 

또 예외인 경우가 2가지이니,  dp[4] = dp[2]*3 + 2 를 해준다. 

 

 

4️⃣ n=6

 

n=4일때부터 예외인 경우는 타일이 계속 붙으면서 점점 증가하게 된다.

그래서 n=6일때는 (예외를 제외한 경우의 수 + n=4일때 옆에 붙을 dp[2]의 경우의 수 + n=6일때 예외 경우의 수)를 계산해줘야 한다.

 

dp[6] = dp[4] * 3 + dp[2]*2 + 2

 

---

구현

 

설계한 방법대로 코드를 구현해보자.

 

처음 내가 만들었던 코드인데, 왜인지 모르겠는데 백준에서 계속 런타임에러가 났다........

 

난 어차피 짝수만 계산하면 되니 dp[0] => n=2인 경우의 수, dp[1] => n=4인 경우의 수 이런식으로 dp배열의 크기를 반으로 줄여서 하려고 했다. 하지만 런타임에러,,,,,

 

let N = Int(readLine()!)!

var dp = [Int](repeating: 0, count: max(N/2+1, 2))
dp[0] = 3
dp[1] = 11

var tmp = 0

if N>2 {
    for i in 2..<N/2{
        tmp+=dp[i-2]*2
        dp[i] = dp[i-1]*3+2 + tmp
    }
}

print(N%2==0 ? dp[N/2 - 1] : 0)

 

그래서 코드를 좀 수정해서 다시 시도했더니 통과했다... 배열의 크기 때문인가?

 

---

전체코드

let n = Int(String(readLine()!))!
var dp = Array(repeating: 0 ,count: 31)

dp[0] = 1
dp[2] = 3

for i in stride(from: 4, through: n, by: 1){
  dp[i] = dp[i - 2] * 3
  for j in  stride(from: 4, through: i, by: 2){
    dp[i] += dp[i - j] * 2
  }
  }
print(dp[n])