[Swift] 백준_01타일(1904)

문제

 

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

1904번: 01타일

 

 

풀이

 

이전에 풀었던 문제와 비슷하게 접근했다. 각 경우마다 앞에 1이 있을 때 뒤에 어떤 것이 올 수 있는지, 00이 있을 때 뒤에 어떤 것이 올 수 있는지를 구해보니 운이 좋게 바로 식을 구할 수 있었다.

 

앞에 1을 붙이면 뒤에 붙을 수 있는 숫자의 개수는 n - 1개이다. 그래서 result[n - 1]의 값을 확인해봤더니 맞았다. 또한 앞에 00을 붙이면 뒤에 n - 2개의 숫자가 붙을 수 있으므로 result[n - 2]의 경우가 들어올 수 있었다.

따라서 식은,

 

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

 

k - 2의 값이 필요하므로 초기값을 result[2]까지 추가하였다. 또한, 마지막 결과에만 15746으로 나눈 값을 출력하면 Int의 범위를 벗어나므로 아예 나머지 값을 result[k]의 값으로 넣어주었다.

import Foundation

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

 

 

_____________________________________________________________________________________________________

 

 

이전과 비슷한 유형이라 식을 비슷하게 접근해봤더니 금방 구할 수 있었다. 문제를 더 많이 풀어보게되면 이전보다 식을 더 빨리 찾을 수 있을 것 같다.