[Swift 알고리즘] 백준 1904 01타일

○ 

다이나믹 프로그래밍 (나는 재귀로 풀어뜸) - Silver 3 

백준 1904 01타일

규칙 찾는데 시간 너무 오래걸림  ㅠ

5 까지는 무난무난. 아 피보나치구나 했는데 확인용으로 6도 계산해보자 하고 6에서 3개 빼먹고 엥 피보나치가 아니었나..? 하고 멍청이짓하다가 시간날림 ㅎ

암튼 결론은 피보나치 수열이다.

 

나는 재귀로 품

// recursion - 69100KB 12ms
let n = Int(readLine()!)

print(tiles(1, 0, 1))
func tiles(_ a: Int, _ b: Int, _ c: Int) -> Int {
    if a == n { return (b + c) % 15746 }
    return tiles(a + 1, c % 15746, (b + c) % 15746)
}

 

근데 dp 문제더라. 뭐 상관은 없지만?

요게 모범답안인듯

let n = Int(readLine()!)!
var a = 1, b = 2
if n <= 2 { b = n }
else {
    for _ in 2..<n {
        let tmp = a
        a = b
        b = (tmp + b) % 15746
    }
}
print(b)

 

 

첫번째 시도 - 런타임 에러 : Thread 1: Swift runtime failure: arithmetic overflow

숫자가 커지면 런타임 에러 난다. 따라서 숫자에 15746으로 나눈 나머지를 넣어줘야함.

print(tiles(1, 0, 1))
func tiles(_ a: Int, _ b: Int, _ c: Int) -> Int {
    if a == n { return b + c }
    return tiles(a + 1, c, b + c)
}

 

** 15746 으로 나눈 나머지 넣어주는 이유?

https://www.acmicpc.net/board/view/76982