[백준] (Swift) 1463번 - 1로 만들기 (스위프트, DP, 동적계획법)

문제 링크

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

1463번: 1로 만들기

 

내가 푼 풀이

• bottom up 방식으로 문제 풀이
• dp 배열의 인덱스가 숫자를 뜻하고, value가 그 인덱스까지 도달할때 최소 경우의 수이다. 즉, dp 배열에는 그 숫자까지 도달할때의 경우의 수를 메모이제이션 해두는 것이다.
• 1번규칙 (3으로 나누어 떨어진다) dp[n] = d[n/3] +1 바로 직전 (3의배수니까 n/3) 경우의 수 에서 1을 더해주는 것
• 2번규칙 (2로 나누어 떨어진다) dp[n] = dp[n/2] +1
• 3번규칙 (1을 뺀다) dp[n] = dp[n-1]+1 1을 빼는 건, 단지 바로 전 숫자에서 연산을 하는 것이라 n-1이고, 1을 뺐다는 경우를 더해주어야 하기 때문에 +1이다. (주의: 배열의 value는 경우의 수이다)
• 작은 문제부터 큰문제로 풀어가는 방식이라고 생각. 그래서 배열을 활용함. (1에서 2로갈때의 경우의수 중 가장 작은 경우의 수, 2에서 3으로 갈때 경우의 수 중 가장 작은 경우의수,,, 그래서 for 문을 활용한다)

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

for i in 2..<n+1 {
    dp[i] = dp[i-1] + 1
    if i % 3 == 0 {
        dp[i] = min(dp[i], dp[i/3]+1)
    }
    if i % 2 == 0 {
        dp[i] = min(dp[i], dp[i/2]+1)
    }
}

print(dp[n])

 

 

우선 동적계획법 (다이나믹 프로그래밍, DP) 에 대한 개념이 전혀 없었기 때문에, 인터넷의 힘을 조금 빌려 문제를 풀었다. 아래 해당 알고리즘을 풀이하기 전에 내가 정리해둔 dp  관련 포스팅을 우선 습득 한 후, 문제를 풀어야 했다.

다이나믹 프로그래밍 (동적 계획법, DP) 기본 개념 공부하기

[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

 

막연하게 피보나치 함수를 활용하여 개념을 공부했다고 문제가 무조건적으로 풀리진 않았다. 역시나 개념을 알고, 이것을 내 것으로 만들기 위해서는 더 많은 연습과 문제풀이, 노력이 필요한 것 같다.