[출처] https://www.acmicpc.net/
알고리즘 분류 : 다이나믹 프로그래밍
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제 입출력
접근
dp 문제이다.
한번에 하나씩 연산해서 1에 접근하는 문제로, 한번 연산한 값을 계속 저장했다가 다시 사용하는 식으로 풀어야되는 즉, dp 문제이다
접근방법은 다음과 같다.
- 반복문을 돌면서 i 번째(2부터 반복하는 수)를 구한다.
- 1로 가는 최소 값을 구하는 것이므로 위에서 주어진1,2,3번 연산을 전부하면서 각각의 결과값이 나오는데 사용된 연산횟수를 구해준다.
- 각 연산횟수중에서 작은 쪽을 선택한다.
bottom-up 방식으로 1부터 n까지 가는 식으로 구성을 했다.
즉, dp[n]은 1부터 n까지 가는데 걸리는 연산수이다.
과정을 말로 풀어쓰면 위와 같은데 이해가 잘 안될것이다.
dp에는 인덱스 번호값의 연산횟수가 저장된다.
dp[2] =1 이면 입력값으로 부터 2에 도달하는데에 1번의 연산을 실행했다는 뜻이다.
문제의 조건에서 1을 빼는 경우를 생각해보겠다.
dp[i]를 구하려면 dp[i-1]의 값에 +1을 해야된다.
i를 3이라고 가정하면, i-1은 2가 된다.
3에서 2로 가는 연산의 수는 1을 빼는 경우가 있기 때문에 +1만큼 차이가 나기때문에 +1을 해준것이다.
3으로 나누어떨어지는 경우랑 3으로 나누어 떨어지는 경우도 마찬가지이다.
다만 이 경우들은 -1하는 경우보다 연산을 적게하면서 동일하게 줄일수 있기 때문에 -1을 뺀경우랑 비교를 해줘야 한다.
예를 들어보겠다.
-1하는 경우로 6에서 2로 가려면 -1,-1,-1,-1 총 4번의 연산이 필요하다.
하지만 2로 나누는 경우는 1번의 연산으로 3이 되고, 여기서 -1을 하면 2에 도달, 즉 2번의 연산이 필요하다.
3으로 나누는 경우는 1번이면 된다.
따라서 가장 큰 연산의 수가 나오는 -1의 경우를 먼저 i번째 저장을 해둔다.
이 말은 dp[i]에는 -1을 해서 i에 도달하는 연산수가 담긴다는 뜻이다.
이게 최소의 연산 수가 아니기 때문에 그 다음으로는 2로 나누는 경우를 생각한다.
2의 경우, 나누어 떨어지면 나눈다고 되어있으므로 %연산을 이용해서 나누어 떨어지면 연산을 수행해준다.
기존에 저장되어있는 -1로 i를 만든 연산수인 dp[i]와 dp[i//2]+1을 비교해서 작은쪽을 선택해서 업데이트 해준다.
2로 나누는 경우로 연산을 수행하면 i는 i//2에서 한번의 연산이 수행되어 나온것이므로 dp[i//2]+1 이렇게 나타낸다.
크기 비교는 min으로 한다.
그 다음으로 더 작은 연산수가 나오는 후보인 3으로 나누는 경우와 비교해준다.
3으로 나누는 경우도 위와 동일하게 연산하면된다.
이렇게 해서 n번째(입력값)을 구해서 출력해주면 된다.
import sys
n = int(sys.stdin.readline())
#여기에는 계산한 횟수를 더하는것이다
dp = [0]* (n+1)
for i in range(2,n+1):
dp[i] = dp[i-1] + 1
if i%2 == 0:
# -1한경우랑 //2 한 경우 둘중에 작은 것으로 업데이트
dp[i] = min(dp[i],dp[i//2]+1)
if i%3 == 0:
# -1한경우랑 //3 한 경우 둘중에 작은 것으로 업데이트
dp[i] = min(dp[i],dp[i//3]+1)
sys.stdout.write(str(dp[n]))
결과
조금 헷갈리긴 했는데 dp의 기본적인 유형이라서 어렵지않게 풀었다.
