문제 설명
•
아래 연산 세 개를 적절히 사용해서 1을 만드는 연산 횟수의 최솟값을 구하는 문제
1.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
2.
X가 2로 나누어 떨어지면, 2로 나눈다.
3.
1을 뺀다.
예제 입력/출력
•
입력1
2
Plain Text
복사
•
출력1
1
Plain Text
복사
•
입력2
10
Plain Text
복사
•
출력2
3
Plain Text
복사
제약 조건
•
문제 풀이
접근1 브루트 포스 (완전 탐색) -
접근2 그리디 (Greedy)
접근3 동적 계획법 (DP) -
풀이 코드
N = int(input())
dp = [0] * (N + 1)
dp[1] = 0
for i in range(2, N + 1):
dp[i] = dp[i - 1] + 1
if i % 2 == 0:
dp[i] = min(dp[i] , dp[i // 2] + 1)
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1)
print(dp[N])
Python
복사