https://www.acmicpc.net/problem/1463
문제 접근
정수가 주어졌을 때 3으로 나누거나, 2로나누거나, 1을 빼는 세 연산을 이용해서 가장 효율적으로 1을 만드는 문제이다.
시간 제한이 0.15초로 짧아 보인다.
메모이제이션 없이 재귀적으로 풀면 시간제한에 걸릴 것 같다.
동적프로그래밍을 이용해야 한다.
dp[] 배열을 만든다.
dp 배열을 dp[10] 이라면 10을 받아 1을 만들때 걸리는 최소 시행 횟수이다.
dp[i]는 다음과 같은 점화식을 갖는다.
dp[i]는
1. dp[i-1]에 1을 더한것
2. dp[i//2] 에 1을 더한것 (i가 2로 나누어 떨어진다면)
3. dp[i//3] 에 1을 더한것 (i가 3으로 나누어 떨어진다면)
이 세가지 수중에 가장 작은 수를 가진다.
해답 및 풀이
import sys
x = int(sys.stdin.readline())
dp = [0] * (x + 1) # x+1개로 선언하는 이유는 인덱스 0번째는 제외하고 싶기 때문
for i in range(2, x + 1):
# 현재의 수에서 1을 빼는 경우
dp[i] = dp[i - 1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
dp[i] = min(dp[i], dp[i // 2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1)
print(dp[x])
Frontend Engineers