다이나믹 프로그래밍 - 1로 만들기(Swift)

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

문제

저작권 문제가 될 수 있어 문제는 삭제합니다.

 

풀이 코드

//input
var n = 26

// 입력조건 최대값 30000 + 1 크기의 dp테이블 선언
var dp = Array(repeating: 0, count: 30000 + 1)

// 시작을 2로 하는 이유는
// 1을 만들어야 하기 때문에 0과 1은 계산 X
for i in 2..<n+1 {
    
    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)
    }
    if i % 5 == 0 {
        dp[i] = min(dp[i], dp[i / 5] + 1)
    }
}

print(dp[n]) // 3

/*
 i 1을 빼는 경우
 2      1
 3      2
 4      3
 5      4
 6      5
 dp[i] = d[[i - 1] + 1 // 1을 빼준 경우 1회 +1
 
 i 2로 나눠질 경우
 2      1
 3
 4      2
 5
 6      3
 dp[i] = d[[i / 2] + 1 // 2로 나눈 경우 1회 +1
 
 i 3으로 나눠질 경우
 2
 3      1
 4
 5
 6      2
 dp[i] = d[[i / 3] + 1 // 3으로 나눈 경우 1회 +1
 
 i 5로 나눠질 경우
 2
 3
 4
 5      1
 6
 dp[i] = d[[i / 5] + 1 // 5로 나눈 경우 1회 +1
 
 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
 n = 6 일때
 
 idx = |0|1|2|3|4|5|6|
 dp  = |0|0|0|0|0|0|0|
 
 i = 2
 1을 빼는 경우 -> dp[i-1] + 1 = 1
 2로 나눠지는 경우 -> dp[i/2] + 1 = 1
 둘중 작은 경우 1
 idx = |0|1|2|3|4|5|6|
 dp  = |0|0|1|0|0|0|0|
 
 i = 3
 1을 빼는 경우 -> dp[i-1] + 1 = 2
 3으로 나눠지는 경우 -> dp[i/3] + 1 = 1
 둘중 작은 경우 1
 idx = |0|1|2|3|4|5|6|
 dp  = |0|0|1|1|0|0|0|
 
 i = 4
 1을 빼는 경우 -> dp[i-1] + 1 = 2
 2로 나눠지는 경우 -> dp[i/2] + 1 = 2
 둘중 작은 경우 2
 idx = |0|1|2|3|4|5|6|
 dp  = |0|0|1|1|2|0|0|
 
 i = 5
 1을 빼는 경우 -> dp[i-1] + 1 = 3
 5로 나눠지는 경우 -> dp[i/5] + 1 = 1
 둘중 작은 경우 1
 idx = |0|1|2|3|4|5|6|
 dp  = |0|0|1|1|2|1|0|
 
 i = 6
 1을 빼는 경우 -> dp[i-1] + 1 = 2
 2로 나눠지는 경우 -> dp[i/2] + 1 = 2
 3으로 나눠지는 경우 -> dp[i/3] + 1 = 2
 둘중 작은 경우 2
 idx = |0|1|2|3|4|5|6|
 dp  = |0|0|1|1|2|1|2|
*/

 

문제 풀이

주석 참고