[Swift 알고리즘] 백준 1463 1로 만들기

△

다이나믹 프로그래밍 - Silver 3 (50분)

 

백준 1463 1로 만들기

문제
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

첫 번째 시도 

엥 이게 왜 실버 3이지? 

아주 순수하게 3의 배수이면 3으로 나누고, 2의 배수이면 2로 나누고 둘 다 아니면 -1 을 순서대로 해주었더니

10에서 3이 아닌 4가 출력이 되어버린다.. 

풉 이렇게 쉬울 줄 알았니? 

 

두 번째 시도

그렇다면 거꾸로 해보자 

1에서 부터 시작해 n을 넘지 않을 때까지 3을 곱해주거나, 2를 곱해주거나, +1을 해주거나

이렇게 하면 어떻게 되는거지?

10은 통과하는데 15는 안된다. 4가 출력되어야 하는데 8이 출력됨..

 

세 번째 시도

흐음... 

더 생각하다가 내 스스로 답을 찾을 수 있었을지 궁금한데

알고리즘 분류가 다이나믹 프로그래밍으로 되어 있는 것을 봐버렸다 ㅠㅠ

(그래서 결국 풀긴 풀었지만 세모 처리함 ㅎ)

여기서 힌트를 얻고 dp 에다 1부터 하나씩 저장해서 이전에 저장된 값과 비교할 수 있도록 구현해주었다. 

3의 배수면 index를 3으로 나누었을 때, 2의 배수면 index를 2로 나누었을 때, 둘 다 아니면 전 index 에서 1을 더해주었을 때 dp 배열의 index에 저장되어 있는 값들 중에서 최소값을 구해 저장해두면 된다. 

 

 

내 답안 - 76916KB 64ms

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

for i in 1...n {
    if i < 4 {
        dp[i] = (i == 1) ? 0 : 1
        continue
    }
    var temp = [n, n, n]
    if i % 3 == 0 {
        temp[0] = dp[i/3] + 1
    }
    if i % 2 == 0 {
        temp[1] = dp[i/2] + 1
    }
    temp[2] = dp[i-1] + 1
    dp[i] = temp.min()!
}

print(dp[n])

 

 

모범 답안 76916KB 20ms

우선 전 index 값에서 +1을 해준걸로 값을 초기화 해주고 2의 배수일 때, 3의 배수일 때 각각 최소값만 비교해주면 됨.

if let n = Int(readLine()!) {
    var dp = Array(repeating: 0, count: n + 1)
    if n > 1 {
        for i in 2...n {
            dp[i] = dp[i - 1] + 1
            if i % 2 == 0 {
                dp[i] = min(dp[i], dp[i / 2] + 1)
            }
            if i % 3 == 0 {
                dp[i] = min(dp[i], dp[i / 3] + 1)
            }
        }
    }
    print(dp[n])
}