정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
dp문제는 아직도 많이 어렵게 느껴진다. 그래서 계속 dp문제들을 풀어보는 중인데, 이 문제는 dp문제 중 기본으로 중요한 문제라고 한다.
처음에는 별 생각없이 for문과 if문을 통해 3, 2로 나누고 1을 빼주는 코드를 구성했다. 하지만 문제 예시의 10의 경우 계속 틀린 답을 내놓았는데, 이 부분을 생각해보는 게 어려웠다.
그래서 다른 풀이를 봐가며 힌트를 얻었는데, 이러한 방식의 아래에서부터 위까지 풀어나가는 방식을 Bottom-Up 이라고 한다.
접근 방식은 다음과 같다.
숫자를 하나씩 증가시켜가면서 최소 단계 수를 구한다.
이때 컨셉은 과거의 배수들 정보를 가져오면서 현재 수의 최소 단계 수를 구하는 것N이라는 수는 N//3을 연산전으로 돌리면, 즉 +1을 하면 만들 수 있다.
N이라는 수는 N//2을 연산전으로 돌리면, 즉 +1을 하면 만들 수 있다.
N이라는 수는 N-1을 연산전으로 돌리면, 즉 +1을 하면 만들 수 있다
이를 이용한 코드는 다음과 같다.
n = int(input())
dp = [0]*(n+1)
for i in range(2, n+1):
dp[i] = dp[i-1] + 1
if i%2 == 0 and dp[i] > dp[i//2] + 1:
dp[i] = dp[i//2] + 1
if i%3 == 0 and dp[i] > dp[i//3] + 1:
dp[i] = dp[i//3] + 1
print(dp[n])
메모리는 37012kb, 시간은 552ms로 적당한 결과가 나왔다.