[다이나믹 프로그래밍] 백준 실버3 1463번: 1로 만들기(Swift)

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

1463번: 1로 만들기

풀이과정

먼저, 몇가지 수를 직접 계산해 보았다.

정수 N의 범위는 [1<= N <=1000000] 이기 때문에, 1부터 10정도 까지만 시도했다.

1은 1이기 때문에 => 0 

2는 2/2 = 1 -> 1 이기 때문에 => 1

3은 3/3 =1 -> 1 이기에 => 1

4는 4/2 = 2 -> 2/2 = 1 -> 1 => 2

5는 5 -1 = 4 -> 4/2 = 2 -> 2/2 = 1 -> 1 => 3

6은 6/3 = 3 -> 3/3 = 1 -> 1 => 2

이정도면, 규칙성이 보인다. 1, 2, 3은 각 0, 1, 1이고,

4부터는 2또는 3으로 나누거나 빼기 1을 하면 미리 계산했던 값이 되는것을 알 수 있다.

규칙성을 좀더 한눈에 보기위해

2는 2/2 = 1 -> 1 이기 때문에 => 1

3은 3/3 =1 -> 1 이기에 => 1

4는 4/2 = 2 -> 2/2 = 1 -> 1 => 2

5는 5 -1 = 4 -> 4/2 = 2 -> 2/2 = 1 -> 1 => 3

6은 6/3 = 3 -> 3/3 = 1 -> 1 => 2

좀더 눈에 보일것 이라 생각된다.

위와 같이 4이상의 수 부턴 그전 결과값을 이용할 수 있다.

마지막으로, 9와 10을 보면

9는 9/3 = 3 -> 3/3 = 1 -> 1 => 2

10은 10 -1 = 9 -> 9/3 = 3 -> 3/3 = 1 -> 1 => 3 

위와 같이 규칙성이 나타난다.

최소값이기 때문에 1 뺀값과 3과 2로 나눈값 중 작은 값을 찾아 출력하면 된다.

let x = Int(readLine()!)!

if x == 1 {
  print(0)
} else if x == 2 {
  print(1)
} else if x == 3 {
  print(1)
} else {
  var dp = [Int](repeating: 0, count: x + 1)
  dp[1] = 0
  dp[2] = 1
  dp[3] = 1
  
  for i in 4...x {
    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)
    }
  }
  print(dp[x])
}