백준 1463번: 1로 만들기 - Swift 풀이

오늘의 문제

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

ㅋㅋ 하... 실환가 진심 풀다가 화딱지 나서 죽을 뻔했네요

 

내 풀이

import Foundation

var N: Int = Int(readLine()!)!
var dp: [Int] = Array(repeating: 0, count: 1_000_001) // 10의 6제곱까지 받을 수 있게

dp[0] = 0
dp[1] = 0 // 초기값 설정

func solution(N: Int) {
    for i in 2...N { // DP 바텀업 방식 : 작은 문제 -> 큰 문제로 상향식
        dp[i] = dp[i - 1] + 1 // 기본 값
        if i % 3 == 0 { // i가 3의 배수면?
            if dp[i / 3] < dp[i] { // 근데 그게 dp[i]보다 더 최적이면?
                dp[i] = dp[i / 3] + 1 // 그래 너 dp[i]
            }
        }
        if i % 2 == 0 { // i가 2의 배수면?
            if dp[i / 2] < dp[i] { // 근데 그게 dp[i]보다 더 최적이면?
                dp[i] = dp[i / 2] + 1 // 그래 너 dp[i]
            }
        }
    }
}

if N > 1 {
    solution(N: N)
}

print(dp[N])

푸는 데에 제 기력을 다 써버린 관계로... 주석만 달아놓겠습니다...

DP로 풀어야 하고... 바텀업 방식으로 해야만 하는 것 같습니다... 아마...

 

제가 계속 i가 2의 배수일 때를 else if로 달아두고 풀었는데~ if로 해야만 정답이 됩니다! ^ ^

i가 2와 3의 공배수일 때는 둘 다 확인해봐야 하기 때문~! if문 2개는 순서가 바뀌어도 결과에는 영향을 미치지 않습니다. 어차피 첫번째 if문에서 갱신된 dp[i] 값을 가지고 두번째 if문에서 사용하고, 어차피 그 중 최소값만 취하기 때문에~~ 하하

 

행복하세요...