문제
정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
1) X가 5로 나누어떨어지면, 5로 나눈다.
2) X가 3으로 나누어 떨어지면, 3으로 나눈다.
3) X가 2로 나누어 떨어지면, 2로 나눈다.
4) X에서 1을 뺀다.
정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들어야한다. 이 연산을 사용하는 횟수의 최솟값을 출력해라.
X = 26일 경우
1. 26 - 1 = 25
2. 25 /5 = 5
3. 5 / 5 = 1
입력
첫째 줄에 정수 X이 주어진다. (1<=X<=30,000)
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
입력 예시
26
출력 예시
3
풀이
이 문제도 생각보다 많은 시간을 썼는데 여기서 DP 문제를 풀 때 어떤 식으로 생각해야되는지 조금은 실마리를 잡은 듯 했다.
2,3,5 각 숫자들로 나누어 떨어지는 경우와 1로 빼는 경우 이렇게 2가지로 생각해보자
주어진 숫자에서 1을 빼고 1을 만드는 경우와 2,3,5로 나누어 떨어져서 먼저 나눈뒤 1로 만드는 걸 진행하는 경우 이 두가지를 비교해가면서 더 작은값을 dp배열에 저장해 나가면 된다.
주어진 값이 6일때,
1부터 시작하면 1은 그 자체로 1이므로 dp =[0,0] 이다. 배열의 인덱스 = 주어진 값이다.
2는 1을 빼고 진행하는 경우와 2를 나누고 진행하는 경우 2가지가 있는데 각 각 비교해보면 1을 빼고 진행하는 경우는 (2-1)일때 1로 만드는 경우에서 1가지를 더한 d[1] + 1, 바로 2로 바로 나누는 경우 (2//2)일때 1로 만드는 경우에서 1을 더한경우 d[2//2] +1 두 값 중 최솟값이다.
3인 경우에도 (3-1)일 때 1로 만드는 경우에서 1가지를 더한 d[(3-1] + 1, 3으로 나눈 뒤 1로 만드는 경우 d[3//3] + 1두 값 중 최솟값을 저장.
4인 경우 d[4-1] + 1, d[4//2] + 1 중 최솟값
이 순서로 진행 시 dp =[0, 0, 1, 1, 2, 1, 3] 이렇게 저장되어 6인 경우의 최솟값은 3이 된다.
풀이코드
import sys
input = sys.stdin.readline
n = int(input())
cnt = [0] * 30001
for i in range(2, n+1):
cnt[i] = cnt[i-1] + 1
if i % 5 == 0:
cnt[i] = min(cnt[i],cnt[i//5]+1)
if i % 3 == 0:
cnt[i] = min(cnt[i],cnt[i//3]+1)
if i % 2 == 0:
cnt[i] = min(cnt[i],cnt[i//2]+1)
print(cnt[n])