[Swift][DP] 백준 2133번 (타일 채우기)

요구능력 : DP에대한 이해

 

코드설명 : 

 

그림을 보면 n = 2일 때는 3가지

n = 3일 때는 0가지,

n = 4일 때는 11가지가 나온다.

n이 홀수일때는 0가지라는걸 직접 그리는걸 시도해보면 알것이다.

 

n = 4일 때를 보면 빨간색으로 색칠한 부분 오른쪽을보자.

n = 2일 때의 모양들을 가지고 있다.

n = 2일 때의 모양이 3번 연속나오니까

dp[i] = dp[i - 2] * 3이라는 식은 쉽게 나온다.

 

하지만, 여기서 끝이아니고 맨 오른쪽에 기괴한 모양이 있다.

이 문제에서 핵심은 저 모양을 처리해주는 것이다.

 

기괴한 모양은 그려보면 알겠지만, n = 4일 때부터 2개씩 계속나온다.

그럼 +2를 해주면 되지않는가 싶지만 아쉽게도 저 모양마저 계속 옆에 모양이 달려서 나올 것이다.

 

그럼 n = 6에서 식은 어떻게되나 살펴보자

dp[6] = dp[6 - 2] * 3 + dp[6 - 4] * 2 + dp[6 - 6] * 2 가 나온다.

dp[6 - 2] * 3 부분은 위에서 구한 기괴한 모양을 제외하고의 수를 구해주는 부분이고

dp[6- 4] * 2는 위의 그림에서 n = 6일 때를 보면 결국 dp[2]개가 2개가 들어간다는 부분이다.( 기괴한 모양 하나에 dp[2]만큼의 경우의수가 더생긴다는 의미이다. 길이가 6이라고 생각했을 때 이전에 있던 기괴한 모양을 가져오면 위의 그림처럼 길이가 4를 차지하는데 나머지 길이가 2니까 dp[2]의 개수인 3이 기괴한 모양의 개수에따라 더해지는거라고 보면된다.)

마지막으로 dp[6 - 6] * 2는 n = 6일때 생성되는 기괴한모양 2개를 의미한다.

 

n은 1부터 30인데 왜자꾸 dp[0]을 이용하는지 궁금한 사람들이 있을것이다.

dp[0]은 그냥 길이가 0이면 완성할 방법은 1개 라고 생각하는게 좋은듯하다.

잘은 모르겠지만 이 문제에서는 그렇게 활용을 하는거같다.라는 식으로 넘기는게 정신건강에 이롭다.

 

후기 : 저번에 풀어본 문제중에 타일채우기가 몇개있었는데 이건 살짝 심화문제..? 느낌이다. 이전것들 보다는 확실히 꼬여있는 느낌..

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])