[백준] Swift 1309 동물원 DP

문제 :

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

1309번: 동물원

 

분석 :

처음엔 N은 주어졌는데 사자의 수가 주어지지 않아서 어떻게 푸는건지 당황했었다. 근데 동물 수와 상관없이 모든 경우의 수를 구하는 것이었다. 그래서 동물이 한마리일경우, 2마리일 경우 .. 로 생각해보았는데 규칙을 찾기 쉽지 않았다. 결국 점화식 세우는 것이 도무지 감이 잡히지 않아 다른 블로그를 보고 풀었다 ㅜ

동물의 수가 아닌 문제에 주어진 조건 N을 가지고 나눠 생각해보자

우선 동물원의 N = 1인 경우,

N번째 줄에 사자는 없다, 왼쪽, 오른쪽 이 3가지 경우의 수를 지닌다. N=1 -> 3

N = 2인경우,

현재 2번째 줄도 마찬가지로 없다, 왼쪽, 오른쪽 3가지 경우의수를 지닌다.

1) 현재 줄에 사자가 왼쪽에 있는 경우는 사자는 없다, 오른쪽의 경우의 수만 지닌다 -> 2

2) 현재 줄에 사자가 오른쪽에 있는 경우는 사자는 없다, 왼쪽의 경우의 수만 지닌다 -> 2

3) 현재 줄에 사자가 없는 경우 사자는 없다, 왼쪽, 오른쪽의 경우의 수를 지닌다 -> 3

 

따라서 이를 점화식으로 나타내면 아래와 같다.

d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2]
d[i][1] = d[i-1][0] + d[i-1][2]
d[i][2] = d[i-1][0] + d[i-1][1]

 

Swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/04/16.
//

import Foundation
var n = Int(readLine()!)!
var d: [[Int]] = Array(repeating: Array(repeating: 0, count: 3), count: n+1)
var mod = 9901
func placeLion() -> Int {
    d[1][0] = 1 // n이 1일때 0 - 사자 x
    d[1][1] = 1 // 사자 왼쪽에
    d[1][2] = 1 // 사자 오른쪽에
    for i in 2..<n+1 {
        d[i][0] = (d[i-1][0] + d[i-1][1] + d[i-1][2]) % 9901
        d[i][1] = (d[i-1][0] + d[i-1][2]) % 9901
        d[i][2] = (d[i-1][0] + d[i-1][1]) % 9901
    }
    return (d[n].reduce(0) { $0 + $1 }) % 9901
}
print(placeLion())