1로 만들기-[이것이 취업을 위한 코딩 테스트다]

📖 문제

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

X가 5로 나누어떨어지면, 5로 나눈다.

1. X가 3으로 나누어떨어지면, 3으로 나눈다.
2. X가 2로 나누어떨어지면, 2로 나눈다.
3. X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
1. 26 - 1 = 25 (4)
2. 25 / 5 = 5 (1)
3. 5 / 5 = 1 (1)

입력 조건

• 첫째 줄에 정수 X가 주어진다. (1 <= X <= 30,000)

출력 조건

• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

Another answer

import sys 
input=sys.stdin.readline

n=int(input())

d=[0]*30001

for i in range(2,n+1):
    d[i] = d[i-1] + 1 
    
    if(i % 2==0): d[i] = min(d[i], d[i//2] + 1)
    if(i % 3==0): d[i] = min(d[i], d[i//3] + 1)
    if(i % 5==0): d[i] = min(d[i], d[i//5] + 1)
    
print(d[n])

풀이

다이나믹 프로그래밍 dp를 너무 예전에 풀어봐서 다시 머리가 초기화됐다... dp는 뭔가 규칙 그러니까 점화식을 알아내서 구현하는 방식인데 이번 문제의 경우 bottom up 방식으로 푸는 문제였다. 

제일 처음 d[0], d[1]의 경우에는 0으로 가정하고 시작한다.

우선 모든 경우 주어진 4개중에 하나로 실행되기 때문에 이 4개를 비교하는 방식을 취하면 된다. 4개를 비교해서 가장 적은 방법으로 가는 것이다. 예를 들어, 26이 들어오면 이 26이 1을빼서 25로 진행하게 될 수도 있고, 2로 나누어 13으로 진행될 수도 있다. 그러나 역순으로 생각하면 1을 빼서 진행하는 것이 25->5->5이런식으로 빠르다는 것을 알 수 있는데 이걸 bottom up방식으로 구현해서 min함수를 이용해 최소값들로 갱신해가며 구하는 방식이었다.

 

자신이 작성한 코드가 교재의 코드와 다른데 맞는지 확인하고 싶으면, 조건을 살짝 수정해서 백준의 "1로 만들기"에 제출하여 알고리즘이 맞는지 확인하면 될 것 같다. 

1463번: 1로 만들기