다이나믹 프로그래밍 - 바닥 공사(Swift)

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

문제

저작권 문제가 될 수 있어 문제는 삭제합니다.

 

풀이 코드

let n = 3

var dp = Array(repeating: 0, count: 1000 + 1)

// n = 1일때 경우의 수
dp[1] = 1
// n = 2일때 경우의 수
dp[2] = 3

for i in 3..<n+1 {
    dp[i] = (dp[i-1] + dp[i-2] * 2) % 796796
}

print(dp[n]) // 5

/*
 # 가로 n , 세로 2 #
 
 덮개의 종류 3가지로 바닥의 가로N이 아래와 같을때 채울수 있는 경우의 수는
 n = 1 일때 경우의 수 => 1
 n = 2 일때 경우의 수 => 3
 n = 3 일때 경우의 수 => 5
 
 덮개중 제일 큰 사이즈가 2x2이기 때문에 N - 2 미만의 길이에 대해서는 고려할 필요 없음
 
 점화식을 구해보면
 i-1 길이까지 덮개가 채워져 있을때 남은 바닥을 채울수 있는 경우의 수는 2x1 사이즈의 덮개 하나밖에 없으므로 경우의 수가 1개가 된다.
 i-2 길이까지 덮개가 채워져 있을때 남은 바닥을 채울수 있는 경우의 수는 1x2 사이즈의 덮개 2개, 2x2 사이즈의 덮개 1개로 경우의 수가 2개가 된다.
 
 dp[i] = dp[i-1] + dp[i-2] * 2
 
 i = 3
 dp[i-1] => 3
 dp[i-2] => 1
 
 dp[i-2] * 2 => 2
 
 최종적으로는 3가지 경우 + 2가지 경우 = 5
 */

 

문제 풀이

주석 참고