백준 1463번 문제(1로 만들기) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

정답 코드는 아래와 같습니다.

import math
 
def solve():
  n = int(input())
  arr = [0, 0, 1, 1]
  for i in range(4, n+1):
    one, two, three = math.inf, math.inf, arr[i-1]
    if i % 3 == 0:
      one = arr[i//3]
    if i % 2 == 0:
      two = arr[i//2]
    value = 1 + min(one, two, three)     
    arr.append(value)
  print(arr[n])
 
solve()
 

 

 

임의의 x 에 대하여 정답(=필요한 연산의 횟수의 최솟값)를 f(x) 라고 할 때,

(정확한 수학적 표현은 아니지만) 아래와 같은 식이 성립함을 알 수 있습니다.

f(x) = 1 + min(f(x/3), f(x/2), f(x-1))

정확한 표현이 되려면 상기 식에 아래 문장이 포함되어야 합니다.

"x가 3으로 나누어 떨어지지 않으면 f(x/3) 이 없다고 가정하고, 2로 나누어 떨어지지 않으면 f(x/2) 이 없다고 가정한다"

 

위 공식이 성립하는 것을 이해했다면 동적 계획법(DP, dynamic programming)을 활용하여 풀면 됩니다.

저는 bottom-up 방식으로 구현하였습니다.

원래는 나누어 떨어지는 경우 각각에 대해서 if 문을 활용해서 구현해야 할텐데,

min 에서 math.inf 가 의미가 없다는 것을 활용하여 식을 조금 간단하게 표현할 수 있었습니다.

 

728x90

 

혹시 위 식이 왜 성립하는지 잘 이해가 안 되는 분들도 있을 수 있습니다.

이것은 꼭 이 문제에서 뿐만 아니라 다른 경우에도 항상 저런 "식"은 추상화된 것인데,

추상화는 구체화보다 잘 이해가 되지 않기 마련입니다.

따라서 잘 이해되지 않는다면, 몇 가지 실제 숫자들에 대해서 직접 해보는 것(구체화)을 추천합니다.

구체화의 반복을 통하여 추상화하는 능력을 기를 수 있습니다.

 

예를 들어 문제 예시에 있는 10을 생각해보겠습니다.

10은 3으로 나누어 떨어지지 않으므로 연산 법칙 2번 또는 3번을 적용하면 5 또는 9가 됩니다.

어떤 연산을 적용하는게 더 빠르게 1이 되는 방법일까요?

현재는 모릅니다만 어찌되었건, 5를 1로 만드는데 필요한 연산의 횟수의 최솟값을 f(5) 라고 하고,  9를 1로 만드는데 필요한 연산의 횟수의 최솟값을 f(9) 라고 하면, 확실한건 f(5)와 f(9) 중에서 더 작은 값에 1을 더한 값이 10을 1로 만드는데 필요한 연산의 횟수의 최솟값(f(10))이라는 것을 알 수 있습니다.

 

 

풀이는 아래 영상을 참고 바랍니다.

www.youtube.com/watch?v=MsU1WeBAf2o

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)