처음에는 아래처럼 모든 경우의 수를 더해서 문제를 풀어보고자 했습니다. 1과 2를 순서에 맞추어 나열하는 문제와 동일하므로 (1칸 이동의 횟수 + 2칸 이동의 횟수)! / (1칸 이동의 횟수)! * (2칸 이동의 횟수)!로 계산하면 답을 수할 수 있습니다.
하지만 이 경우 n이 너무 커지게 되면 factorial을 계산할 때 arithmatic overflow 에러가 발생해서 풀이가 불가능했습니다.
arithmatic overflow를 방지하기 위해서 문제에서 1234567로 나눈 값을 리턴하라고 했지만 factorial과 경우를 수를 구할 때는 곱셈 연산을 사용하므로 이 방식으로는 문제를 풀 수 없습니다.
func solution(_ n:Int) -> Int {
func factorial(_ n: Int) -> Int {
if n <= 1 {
return 1
} else {
return (n * factorial(n - 1))
}
}
func numOfCase(_ one: Int, _ two: Int) -> Int {
factorial(one + two) / (factorial(one) * factorial(two))
}
var one = n
var two = 0
var ans = 0
while one >= 0 {
ans += numOfCase(one, two) % 1234567
one -= 2
two += 1
}
return ans
}
따라서 이 문제는 덧셈과 뺄셈만을 활용해서 풀어야 합니다. dp를 활용하면 됩니다. 초기 값과 점화식은 아래와 같습니다.
// 초기값
f(0) = 1, f(1) = 1
// 0칸을 이동하는 경우, 1칸을 이동하는 경우 모두 1가지
// 점화식
f(n) = f(n - 1) + f(n - 2)
// n칸 이동 = n - 1칸을 이동하고 1칸 이동 + n - 2칸을 이동하고 2칸 이동
func solution(_ n:Int) -> Int {
var cache = Array(repeating: 0, count: n + 1)
func dp(_ n: Int) -> Int {
if n <= 1 {
return 1
}
if cache[n] == 0 {
cache[n] = dp(n - 1) + dp(n - 2)
}
return cache[n] % 1234567
}
return dp(n)
}