BOJ [Silver III] 1로 만들기 - 1463

문제 링크

분류

다이나믹 프로그래밍(dp)

문제 설명

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

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

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

입력

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

10

출력

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

3

아이디어

• 3으로 나눌 수 있으면 3으로 나누는 게 제일 빠르게 줄어들겠지 하고

  while n > 1:
  	if n%3 == 0:
     	n //= 3
         count += 1
     ...
     

  이런 식으로 짜다가, 예시인 10만 해도 우선 1을 빼고 난 뒤에 3으로 나누는 게 빠르니까 경우가 다 다르다는 걸 깨달음

• 10 -> 9 or 5 -> ... 이런 식으로 트리 그려보니까 dp 개념 공부했던 게 생각 남!

• 문제는 어떤 식으로 풀었었는지 정확히 기억 안 나서 dp 개념 정리해둔 글 다시 확인 → 부분 문제의 최적의 해 저장해두는 배열 정의 필요

• d 배열 정의해서,

  • 우선 i-1일 때의 최적의 해+1이 현재 해라고 가정하고
  • i가 3으로 나눠지면 i/3일 때의 최적의 해+1과 현재 값을 비교
  • 2로 나눠지면 i/2일 때의 최적의 해+1과 현재 값을 비교
  • min 값이 i의 최적의 해가 됨

내 코드

n = int(input())
d = [0] * 1000001
d[1], d[2], d[3] = 0, 1, 1
for i in range(4, n+1):
    d[i] = d[i-1] + 1
    if i%3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
    if i%2 == 0:
        d[i] = min(d[i], d[i//2] + 1)
    
print(d[n])

• 입력 조건이 $10^6$까지여서 d를 1,000,000까지로 잡아줬다가 런타임 에러 남

• 최대 입력값인 1,000,000보다 큰 1,000,001로 잡아줘야 함~~