[Swift] 1463 1로 만들기

1463 1로 만들기

문제로 이동

문제 요약

정수 x에 대해 세 가지 연산을 할 수 있다. 연산을 반복하며 x를 1로 만들고자 할 때, 최소한의 연산 횟수를 구해라.

• 3으로 나누어 떨어진다면, 3으로 나눈다.
• 2로 나누어 떨어진다면, 2로 나눈다
• 1을 뺀다.

알고리즘

점화식은 다음과 같다.$$F(n) = min(F(n/3), F(n/2), F(1)) + 1$$

해당 점화식을 사용하여 Bottom up 방식으로 코드를 구현한다.

접근 방법

• 그리디는 왜 안 될까?
• 무조건 나눗셈이 숫자가 더 빨리 줄어들기 때문에 그리디를 생각할 수 있지만, 최적회가 아니다.
  • 그리디 알고리즘은 3으로 나눔 -> 2로 나눔 -> 1로 뺌의 순서로 이루어 질 것이다.
  • 2n + 1을 생각해보자.
    • Greedy: 11 -> 10 -> 5 -> 4 -> 2 -> 1 (6회)
    • 최적해 : 11 -> 10 -> 9 -> 3 -> 1 (5회)
  • 간단한 예제로도 그리디가 최적해가 아님을 밝힐 수 있다.

코드

var dp = [0, 0, 1, 1]
print(makeNumberOne(Int(readLine()!)!))

func makeNumberOne(_ n: Int) -> Int {
    guard n > 3 else { return dp[n] }

    for i in 4 ... n {
        dp.append(dp[i-1] + 1)

        if i % 3 == 0 { // 3으로 나누어 떨어진다면
            dp[i] = min(dp[i], dp[i/3] + 1)
        }
        if i % 2 == 0 { // 2로 나누어 떨어진다면
            dp[i] = min(dp[i], dp[i/2] + 1)
        }
    }
    return dp[n]
}

시간초과 발생 ( filter, sorted 사용)

var dp = [0, 0, 1, 1]
print(makeNumberOne(Int(readLine()!)!))

func makeNumberOne(_ n: Int) -> Int {
    guard n > 3 else { return dp[n] }

    for i in 4...n {
        var nexts = [Int](repeating: -1, count: 3)

        if i % 3 == 0 { nexts[0] = dp[i/3] }
        if i % 2 == 0 { nexts[1] = dp[i/2] }
        nexts[2] = dp[i-1]

        nexts = nexts.filter { $0 != -1 }

        dp.append(nexts.min()! + 1)
    }
    return dp[n]
}