1463번 : 1로 만들기 - Python

문제

https://www.acmicpc.net/problem/1463

풀이

정수 X에 사용할 수 있는 연산 3으로 나누기, 2로 나누기, 1빼기 를 보두 비교해본다. 그중 연산 횟수가 가장 적은 값을 저장해 가면서 X까지 가면 된다.

코드

from sys import stdin

input = stdin.readline

n = int(input())

array = [0 for i in range(n+1)] #array[1]을 1로 사용 할 수 있도록 n+1까지 만든다.

for i in range(2,n+1): #1을 뺀경우, 3으로 나눈 경우, 2로 나눈경우 모두다 비교해 본다.
    array[i] = array[i-1]+1 #1을 뺀 값(i-1)을 1로 만드는 경우가 최소일 수 있다.
    # 1을 뺀 값을 먼저 넣는 경우는 대부분의 경우 1을 빼는 경우가 연산 횟수가 가장 크기 때문이다.
    if i%3==0:
        array[i] = min(array[i], array[i//3]+1) #1을 뺀 값이 최소인지 3으로 나누는 경우가 최소인지 비교한다.
    if i%2==0:
        array[i] = min(array[i], array[i//2]+1) #1을 뺀 값, 3으로 나눈 값, 2로 나눈 값중에 최소인 경우를 비교한다.

print(array[n])

1을 먼저 빼지 않는 코드

from sys import stdin

input = stdin.readline

n = int(input())

array = [i for i in range(n+1)] #array[1]을 1로 사용 할 수 있도록 n+1까지 만든다. 각 정수에서 가장 큰 경우를 넣어둔다.

array[1]=0 #1은 이미 1이므로 연산을 할 필요가 없다. 그래서 0


for i in range(2,n+1): #1을 뺀경우, 3으로 나눈 경우, 2로 나눈경우 모두다 비교해 본다.
    
    if i%3==0:
        array[i] = min(array[i], array[i//3]+1) #3으로 나누는 경우가 최소인지 비교한다.
    if i%2==0:
        array[i] = min(array[i], array[i//2]+1) #3으로 나눈 값, 2로 나눈 값중에 최소인 경우를 비교한다.

    array[i] = min(array[i-1]+1, array[i]) #1을 뺀 값, 3으로 나눈 값, 2로 나눈 값중에 최소인 경우를 비교한다.

print(array[n])