Swift) 백준 1463번 (1로 만들기)

요구능력 : dp의 개념을 알고있느냐

 

코드설명 : 

 

다이나믹 프로그래밍의 바텀업 방식은 작은문제부터 차근차근 답을 도출해 나아가는 방식이다.

그리고 배열에 저장하는 이유는 다이나믹프로그래밍의 기본 원리중 하나인 중복되는 부분문제를 해결하기 위함이다.

2~n 까지의 모든 경우를 배열에 저장해놓고 사용함으로써 중복되는 부분문제를 해결하고 실행시간을 어마어마하게 줄일 수 있다.

만약, 10까지가는 최단경로를 구하고자 하면 2~10까지의 최단경로를 모두 구하는것이다.

 

1. DP방식중 Bottom-up방식으로 접근하기 위해 우선 배열을 선언하였다.

 

2. 3가지의 조건 중 -1을 하는 조건에는 특정조건이 없으므로 우선적으로 처리해준다.

 

3. 현재의 수 i가 2 or 3으로 나누어 떨어지면 2 or 3으로 나눠주는데, 우리가 현재 구하는건 최소의 움직임이다.

그렇기 때문에, 기존에 구해놓은 경로와 비교하여 작은값을 넣어준다.

 

추가>> 1씩 더하는 이유

dp[10]을 구하면 dp[9] + 1이다.

dp[10]에서 dp[9]로 넘어갈때 연산을 한번하기때문이다.

 

추가>> if문을 따로 놓은 이유

2로도 나눠질 수 있고 3으로도 나눠질 수 있는데 그중 최소한의 움직임을 구해야한다.

if~else문으로 하게되면 위에서 2로 나눈다면 아래에서 3으로는 안나누기 때문

 

후기 : DP의 개념을 공부하고 나서는 처음으로 풀어본 DP문제 문제가 DP문제라는것을 아는방법만 체득하면 금방풀수있을거같다.

var n = Int(readLine()!)!
var dp = Array(repeating: 0, count: 1000001) //몇번 움직였는지의 결과를 저장하기위한 배열

if n == 1 {
    print("0")
}else {
    for i in 2...n { //i는 현재 최단경로를 구하고자하는 수
        dp[i] = dp[i - 1] + 1
        
        if i % 2 == 0 {
            dp[i] = dp[i] >= dp[i / 2] + 1 ? dp[i / 2] + 1 : dp[i]
        }
        if i % 3 == 0 {
            dp[i] = dp[i] >= dp[i / 3] + 1 ? dp[i / 3] + 1 : dp[i]
        }
        
    }
    print("\(dp[n])")
}