코딩 퀴즈

이번 코딩 퀴즈는 동적 계획법(Dynamic Programming)을 이용해 주어진 정수 n을 1로 만들기 위한 최소 연산 횟수를 구하는 프로그램을 작성합니다.

연산은 다음 세 가지 중 하나를 선택할 수 있습니다.

1. n이 3으로 나누어 떨어지면, 3으로 나눕니다.

2. n이 2로 나누어 떨어지면, 2로 나눕니다.

3. n에서 1을 뺍니다.

이 3가지 연산을 적절히 사용하여 n을 1로 만드는데 필요한 최소 연산 횟수를 찾는 함수를 작성해 보세요.

Copy
def solution(n):
    # 여기에 코드를 작성하세요
    return

---

• 입력으로 받는 n은 2 이상 10,000 이하의 정수입니다.

• 함수는 반드시 동적 계획법을 사용하여 구현되어야 합니다.

---

• 입력: 10
• 출력: 3
• 설명: 10 -> 9 -> 3 -> 1 과정을 거쳐 총 3번의 연산이 필요합니다.

• 입력: 6
• 출력: 2
• 설명: 6 -> 3 -> 1 과정을 거쳐 2번의 연산이 필요합니다.