문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

문제풀이

과정

• 주어진 문제는 정수 N을 1로 만드는 데 필요한 최소 연산 횟수를 찾는 것이다. 사용할 수 있는 연산은 세 가지:
  1. 3으로 나누기
  2. 2로 나누기
  3. 1 빼기
• DP(동적 프로그래밍,Dynamic Programming: 필요, 문제를 해결하기 위해 하위 문제의 해결 결과를 저장하고 재사용하는 방법론)
  • 중복 계산을 피하고, 전체 문제를 더 효율적으로 해결

코드

N = int(input()) # 입력 
dp = [0] * (N + 1) # 0으로 N+1 크기의 배열 초기화(인덱스 1~N 까지 사용)

for i in range(2, N + 1):
    dp[i] = dp[i - 1] + 1  # 1을 뺀 경우의 연산 횟수
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1) 
        # 2로 나눈 경우, 이전 연산 회수와 비교하여 최소 연산 수로 배열 값 저장
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
        # 3로 나눈 경우, 이전 연산 회수와 비교하여 최소 연산 수로 배열 값 저장
        
print(dp[N]) 

풀이

• dp에 최소 연산 횟수를 저장한다.
• dp[1]은 0.
  • 1을 1로 만드는 데 필요한 연산 횟수는 0이다.
  • range(2, N + 1) 의 이유
• 각 숫자 i에 대해 최소 연산 횟수를 계산:
  1.dp[i] = dp[i - 1] + 1i에서 1을 빼는 경우
  2.dp[i] = min(dp[i], dp[i // 2] + 1) if i는 2으로 나누어 떨어지는 경우
  3.dp[i] = min(dp[i], dp[i // 3] + 1) if i는 3으로 나누어 떨어지는 경우

  • dp[i // 2] 에는 이미 계산된 최소 연산 횟수가 입력되어 있다.
    예를 들어 dp[8]인 경우, 이전 계산을 통해 dp[4]에 최소 연산횟수 결과가 입력되어 있으므로, 별도 연산없이 이를 채택한다. (해결 결과를 저장하고 재사용)