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

백준 1463번

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 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)

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

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

Screen Shot 2021-09-26 at 7 30 17 PM

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

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

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

  1. X가 3으로 나누어 떨어진다면? dp[n] = dp[n/3] + 1
  2. X가 2로 나누어 떨어진다면? dp[n] = dp[n/2] + 1
  3. 1을 뺄 경우? dp[n] = dp[n-1] + 1

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

  1. 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을 만들 수 있다.)

  1. 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])

Screen Shot 2021-09-26 at 10 26 45 PM

이번에도 쉽게 잘 설명해줬던 사이트의 풀이를 참고했당..

동적계획법 문제는 점화식을 세워야한다는 특성을 기억해야할듯!

Reference