[Swift] 백준_2xn 타일링(11726)

문제

 

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

11726번: 2×n 타일링

 

 

풀이

 

n에 따라서 가로 길이가 1씩 늘어난다. 

 

가로가 k라고 가정하고 맨 왼쪽에 가로가 1인 블럭을 둔다고 생각하자. 

이렇게되면 나머지에는 가로가 k-1이고 세로가 2인 공간이 남는다. 

 

result[k]가 가로가 k일때 블럭을 채워넣는 경우의 수라고 한다면 맨 왼쪽에 1짜리를 두면 남은 공간엔 result[k - 1]의 결과가 들어갈 것이다.

 

다음으로, 맨 왼쪽에 가로가 2인 블럭을 두게되면 당연하게 아래에도 가로로 블럭을 놔야한다. 이렇게되면 남은 공간은 result[k - 2]가 될 것이기 때문에 점화식은 다음과 같다.

 

result[k] = result[k - 1] + result[k - 2]

 

이때 주의해야 할 것은, 10007로 나누는 것을 마지막에만 하면 안되고 result에 넣을때 미리 나눠서 넣지 않으면 Int의 범위를 벗어나서 오류가 발생할 것이다.

import Foundation

let n = Int(readLine()!)!
var result = Array(repeating: 0, count: n + 1)
if n <= 2 {
    print(n)
    exit(0)
}
result[1] = 1
result[2] = 2
for i in 3...n {
    result[i] = (result[i - 1] + result[i - 2]) % 10007
}
print(result[n])

 

 

_____________________________________________________________________________________________________

 

 

쉽지않음.