python 백준1463 1로 만들기(BOJ1463)

문제링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

처음에 풀때는 dp테이블 사용해서 반복문으로 풀면 되겠다 싶어서 제출했다

import sys

input = sys.stdin.readline

input_num = int(input())

dp = [0] * 1000001

#초기값
dp[2] = 1
dp[3] = 1

def cal(input_num):
  #3보다 작으면초기값 리턴
  if(input_num <= 3):
    return dp[input_num]

  #그외에는 dp테이블에 저장된 정보로 최소 연산횟수를 구해서 +1 함
  else:
    for i in range(4, input_num+1):
      min_value = int(1e9)
      if i % 3 == 0:
        if dp[i//3] <= min_value:
          min_value = dp[i//3]
      if i % 2 == 0:
        if dp[i//2] <= min_value:
          min_value = dp[i//2]
      if dp[i-1] <= min_value:
        min_value = dp[i-1]
      dp[i] = min_value + 1
      if i == input_num:
        return dp[input_num]
print(cal(input_num))

그런데 시간이 생각보다 길게나왔다

내 제출 시간 404ms 나온다

다른사람들 맞춘걸 보니

다른사람들은 36ms

조금 차이났으면 워낙 고수들이 많으니까 그러려니 할텐데

시간이 거의 10배가 넘게 차이가나서 코드를 봤더니

시간이 짧게나온사람들은 재귀방식을 사용해서 푼것이었다!

내가 푼것처럼 반복문으로 푼걸 보통 바텀업 방식이라고 하고

재귀호출을 통해서 푼걸 탑다운 방식이라고 한단다

import sys

input = sys.stdin.readline

input_num = int(input())

#딕셔너리 사용
dp = {1:0}

def cal(num):
  #값이 이미 있다면 그 값을 사용->함수호출빈도 줄여줌
  if num in dp.keys():
    return dp[num]

  #3과 2둘다로 나눠진다면 둘중 계산빈도가 낮은걸 입력
  if num%3 == 0 and num%2 == 0:
    dp[num] = min(cal(num//3)+1, cal(num//2)+1)
  #3으로만 나눠진다면 3으로 나눈값과 1을 뺐을때의 계산빈도중 낮은걸 입력
  elif num%3 == 0:
    dp[num] = min(cal(num//3)+1, cal(num-1)+1)
  elif num%2 == 0:
    dp[num] = min(cal(num//2)+1, cal(num-1)+1)
  else:
    dp[num] = cal(num-1)+1
  #최소값 리턴
  return  dp[num]
#출력
print(cal(input_num))

보통은 반복문이 재귀보다 빠른걸로 알고있었는데 이 문제같은경우엔 3이나 2로 나누는게 있어서

반복문으로 할때보다 숫자가 훅훅 줄어버려서 그런것같다

이 문제로 바텀업 탑다운 둘 다 연습해볼수있었서 좋았다.