1 분 소요

[Silver III] 1로 만들기 - 1463

문제 링크

성능 요약

메모리: 109244 KB, 시간: 680 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 3월 21일 17:25:28

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

풀이

import sys
input = sys.stdin.readline

X = int(input())
dp = [0] * 10000001

for i in range(2, X+1):
    dp[i] = dp[i-1] + 1 # 1을 빼는 경우,

    if i % 2 == 0:
        # 2로 나누어 떨어지는 경우,
        dp[i] = min(dp[i], dp[i//2] + 1)
    if i % 3 == 0:
        # 3으로 나누어 떨어지는 경우,
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[X])

10을 예로 들자면, 10-> 9-> 3-> 1 연산의 최소값은 3이 된다. 9인 경우에는 9-> 3-> 1 총 2번이고, 3은 3-> 1 총 1번이 된다. 즉 9인 경우의 횟수와 3인 경우의 횟수를 더한 값이 10의 최소 연산 횟수가 된다.

이를 적용하기 위해서는 dp를 이용해야하는데, 먼저 저장할 리스트에 0으로 초기화 해준다. 1은 연산횟수가 0이므로, 2부터 입력받은 X까지 반복문을 설정한다. 이전 값의 연산횟수에 1을 더해줌으로써 1을 빼는 경우의 횟수를 +1해준다. 이후에 2로 나누어떨어지는 경우라면, 방금 1을 빼는 경우의 횟수와 2로 나눈 값의 횟수를 비교하여 더 작은 값을 저장한다. 3도 마찬가지로 같은 원리이다.

예를 들어 i가 3인 경우에 dp[3] = dp[2] + 1이므로 1을 빼는 경우에는 연산 횟수가 2가 된다.(3->2->1) 이후 3으로 나누어 떨어지는 조건문에서는 dp[3] > dp[1](2>1) 이므로 3으로 나눴을 때의 연산이 더 작다.(3->1) 따라서 dp[3]의 최종 값은 3이된다.

댓글남기기

참고