[백준] (Swift) 1309번 - 동물원

문제 링크

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

1309번: 동물원

 

풀이 IDEA

사자가 어디 위치에 오느냐에 따라 새로 들어오는 사자들의 위치가 달라진다. 하지만 이 이전에 단순한 숫자규칙이 있는지 찾아보았다. 예시가 N = 4 일때가 주어졌으니, N=1,2,3 을 찾아보았다.

N=1 일때 3, N=2 일때 7, N=3일때 17이 되었고, N=4일때는 41이 된다고 했다. 이 숫자들을 통해 규칙을 찾아보면, n-1번째 숫자에 2를 곱하고, n-2번째 숫자를 더해주면 n일때의 값이 나온다는 단순한 숫자규칙이 존재한다.

이처럼 dp 문제에서는 규칙을 찾는 것이 매우 중요하다.

 

소스코드 - 맞았습니다!

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count: n+1)

dp[0] = 1
dp[1] = 3

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

print(dp[n])