[이코테] 1로 만들기

다이나믹 프로그래밍의 대표격인 문제라고 한다.

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

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

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

• 입력 조건
  첫째 줄에 정수 X가 주어진다. 1<=X<=30000

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

• 입력 예시
  26

• 출력 예시
  3

솔직히 혼자하다가 아예 진행 자체가 안되서 그냥 답을 봤다. 왠지는 모르지만 다이나믹 프로그래밍 개념을 문제에 적용해서 풀 수가 없었다..

#p217

a = [0] * 30001

x = int(input())

for i in range(2, x + 1):
    a[i] = a[i - 1] + 1

    if i % 5 == 0:
        a[i] = min(a[i // 5] + 1, a[i])

    elif i % 3 == 0:
        a[i] = min(a[i // 3] + 1, a[i])

    elif i % 2 == 0:
        a[i] = min(a[i // 2] + 1, a[i])
        
print(a[x])

답을 베껴쓰고 한참 바라보니, 문제에 대한 내 접근 방법 자체가 틀렸음을 알 수 있었다.
나는 연산한 값을 가지고 (26-1이면 25) 이를 반복문에 적용하여 풀려고 했는데, 전혀 아니었다. 어차피 문제에서 요구하는 것은 최소 계산 횟수이므로 계산한 횟수가 가장 적은 것만을 고려하여 리스트에 저장하고 풀면 되는거였다. 다음에는 스스로 풀어봐야 되겠다.