문제 링크

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

문제 설명

• 주어진 N을 세 가지 연산으로 1로 만들 때 연산 횟수의 최솟값 구하기
• 연산1 : 3으로 나누어 떨어질 때 나누기 3
• 연산2 : 2로 나누어 떨어질 때 나누기 2
• 연산3 : 빼기 1

접근

그리디

• 작아질수록 좋을 것 같음
  • 불가능할 때까지 나누기 3
  • 불가능할 때까지 나누기 2
  • 1이 될 때까지 빼기 1
• 10일 때 '나누기 2'가 아닌 '빼기 1'을 먼저 함
• 다른 방법은 못 찾을 것 같음

DP

• N의 최소 횟수는 어쨌든 그전 값을 이용 (1 더한 것임)
• O(N)으로 끝낼 수 있을 것 같다
• 종료 조건 or bottom 값을 알 수 있다

풀이

• 1일 때 횟수 0
• 2부터 n까지 돌면서
• i일 때 횟수는 min(연산1, 연산2, 연산3) + 1

코드

n = int(input())
min_list = [0] * (n+1)
for i in range(2, n+1):
    case_list = [min_list[i-1]]
    if i % 3 == 0:
        case_list.append(min_list[i//3])
    if i % 2 == 0:
        case_list.append(min_list[i//2])
    min_list[i] = min(case_list) + 1
print(min_list[n])