[Python] 1463번 1로 만들기, 그림 설명, 자세한 설명

✏️ 문제

 

문제 파악

문제에서 나온 연산은 3가지이다.

1. 3으로 나누어 떨어지면 3 배수로 가는 방법
2. 2로 나누어 떨어지면 2 배수로 가는 방법
3. 1 차이로 가는 방법

연산하는 횟수의 최솟값을 구하므로 해당 값으로 가는 3가지 방법 중 연산이 최소로 되는 값을 출력해야 한다.

위의 그림을 기준으로 코드를 짜면 된다.

 

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

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

for i in range(2, n + 1):
  d[i] = d[i - 1] + 1 # 1 차이로 가는 방법, 3번 방법

  if i % 3 == 0:
    d[i] = min(d[i], d[i // 3] + 1) # 3번 방법으로 나온 값과 1번 방법으로 나온 값 중 최솟값을 대입
  if i % 2 == 0:
    d[i] = min(d[i], d[i // 2] + 1) # 3번 방법으로 나온 값과 2번 방법으로 나온 값 중 최솟값을 대입
print(d[n])