백준 1463번 - 1로 만들기

2023-5-30 · 1 min · 113 words · Junha | Suggest Changes

Table of Contents

백준 1463번 바로가기

나의 풀이

n = int(input())
dp = [0]*1000001

for i in range(1,n+1):
  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[n]-1)

CODE REVIEW

문제 자체는 간단하지만 발상이 어려웠던 문제. 한번에 해결하지는 못하고, n에서 1로 내려오는 대신 1에서 n으로 접근하는 방식을 활용해보라는 힌트를 가지고 문제를 해결했다.
직접 1부터 나아가는 그래프를 그려봤는데(위의 사진 참고!) 처음에는 nums라는 dict을 만들어서 if nums in dict: pass else: nums[n]=count라는 식으로 나아갈려고 했는데, 이게 생각보다 고려할게 많아져서 포기했다.
아예 새로 코드를 짜서 문제를 해결했다. for문 안의 순서가 (+1, *2, *3) 순서인데, 3배하는 것이 최소일 확률이 높아서 그렇게 했다.
index와 num을 서로 동일하게 맞추기 위해 dp = [0]*1000001으로 맞춘건 이젠 익숙하다.

Comments: