[알각코] 백준 15649번 - N과 M (1)

백준 1463번

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.

N = int(input())

def divideByThree(num):
  return num // 3

def divideByTwo(num):
  return num // 2

def substractOne(num):
  return num - 1

tot = 0
while N != 1:
  if (N % 3) == 0:
    N = divideByThree(N)
  elif (N % 2) == 0:
    N = divideByTwo(N)
  else:
    N = substractOne(N)
  tot += 1

print(tot)

조건문으로 단순하게 해결해보았던 동적계획법 문제

하지만 틀려따…왜 틀렷지?

다시 계산해보니, 내가 구현했던 단순 조건문은 최소값이 나오는 답이 아니었다. </br>

예를 들어, 숫자 10의 경우, 10 -> 5 -> 4 -> 2 -> 1로 답이 4가 될 수 있지만, 최소값은 10 -> 9 -> 3 -> 1로 3이다.

즉, 동적 계획법으로 풀어야하는데 동적계획법으로 푸려면 점화식을 구해야한다.

X가 3으로 나누어 떨어진다면 3으로 나누어떨어지게할 때 횟수는? dp[n] = dp[n/3] + 1
X가 2로 나누어 떨어진다면 횟수는? dp[n] = dp[n/2] + 1
1을 뺄 경우의 횟수는? dp[n] = dp[n-1] + 1

해당 X의 숫자에서 그 전 숫자의 횟수보다 하나 더 많은 경우를 점화식으로 구하는 것이다.

예를 들어 X를 6이라고 가정하면

6은 3으로 나누어 떨어지므로 dp[6] = dp[2] + 1 (2에서 3을 곱하면 6이된다. 즉 dp[2]에서 3을 곱하는 연산을 한 번 더 하면 6을 만들 수 있다.)

2 .6은 2으로 나누어 떨어지므로 dp[6] = dp[3] + 1 (3에서 2을 곱하면 6이된다. 즉 dp[3]에서 2를 곱하는 연산을 한 번 더 하면 6을 만들 수 있다.)

6에서 1을 빼면 5가 되므로 dp[6] = dp[5] + 1(5에서 1을 더하면 6이 된다. 즉 dp[5]에서 1을 더하는 연산을 한 번 더 하면 6을 만들 수 있다.)

N = int(input())
dp = [0, 0, 1, 1]

for i in range(4, N+1):
  dp.append(dp[i-1]+1)
  if i % 2 == 0:
    dp[i] = min(dp[i//2]+1, dp[i])
  if i%3 == 0:
    dp[i] = min(dp[i//3]+1, dp[i])

print(dp[N])