글 읽기 - 59%에서 자꾸 막히는데 반례혹시 아시는분 계신가요? ㅠㅠ

akdlsjtm21 1년 전 0

else if 도 해보고 if문으로 바꿔봐도 자꾸 59%에서 틀렸다고 나오네요..

혹시 코드에 잘못된 부분이 있을까요??

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

santoo 1년 전 0

3으로 나눴을 때와 2로 나눴을 때, 그리고 1을 뺐을 때 각각의 경우는 우선 순위가 없습니다(값이 금방 줄어든다고 최적의 해가 아닙니다). 따라서 for loop에서 한 바퀴를 돌 때마다 세 가지 경우 중 가장 작은 값을 배열에 할당해주도록 해야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

59%에서 자꾸 막히는데 반례혹시 아시는분 계신가요? ㅠㅠ

akdlsjtm21 1년 전 0

santoo 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말