[Python 백준] 1463 | 1로 만들기

Try to solve 💭

처음엔 정수 x에 1,2에 우선순위를 두어 나누어 떨어지지 않으면 3을 연산하는 방식을 생각했지만, 정수 '10'에서 최솟값이 나오지 않는 예외가 생긴다.
-> 연산순위가 중요한 것이 아니라 연산 결과의 최솟값이 중요한 것이다.

그렇다면 주어진 정수 값에 대해, 3가지 연산을 모두 수행하여 그 중 최솟값을 구하면 될까?
-> 3 or 2로 나누어 떨어지지 않는 수들도 고려하여 조건문을 생성

정수 값이 커질수록 연산량이 상당할 것이다!
-> 결과값을 저장하는 리스트를 생성, 이전 값들의 최소 결과값들을 저장하여 연산량을 줄임

Solution 💡
점화식 이용

1. 입력 받은 값의 크기만큼 리스트 생성
2. 0부터 n까지 조건식을 수행하는 for문 생성
3. 3 or 2로 나누어 떨어지는 값이나 1을 뺀 값 중 최솟값을 리스트에 저장
   -> 처음엔 다음과 같이 수행하였다.

..
  if i % 3 == 0:
    list[i] = list[i//3] + 1
  if i % 2 == 0:
    list[i] = list[i//2] + 1
  list[i] = list[i-1] + 1
..

하지만 최솟값을 고려해야 하기 때문에, 아래 코드와 같이 1을 뺀 값을 저장한 리스트 값과 크기를 비교하는 조건을 추가하여 list에 최종 값을 저장하게 하였다.
( 2,4,5 : 1을 추가하는 이유는 각 연산을 하면 연산 수가 1씩 증가하기 때문! )

Code Review 🔎

n = int(input())
list = [0] * (n+1)

for i in range(0, n+1):
  if i == 0 or i == 1:
    list[i] = 0
    continue
  list[i] = list[i-1] + 1
  if i % 3 == 0 and list[i//3] + 1 < list[i]:
    list[i] = list[i//3] + 1
  if i % 2 == 0 and list[i//2] + 1 < list[i]:
    list[i] = list[i//2] + 1

print(list[n])