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

[Silver III] 1로 만들기 - 1463

문제 링크

성능 요약

메모리: 40224 KB, 시간: 464 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 20일 11:52:22

문제 설명

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

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

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

입력

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

출력

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

---

접근 방식 

 

이전 DP문제를 풀었을 때 다른분께서 DP테이블을 미리 만들고 하는게 좋다고 하셔서 한 번 시도해보려고 한다. 근데 이 문제를 어떻게 DP로 풀어야하는지 잘 모르겠다. 한 시간 정도 씨름한 결과 메인 점화식을 생각해냈다. 진짜 뿌듯했다. 디테일한게 자꾸 틀려서 결국 이전에 생각없이 제출해놓은 답을 봐야했지만 만족

 

dp는 손으로 적어봐야 한다는게 무슨 말인지 몰랐는데 그려보니까 확실히 보이더라. min을 사용해서 dp[i-1] + 1 값이랑 2로 나눠서 dp[i//2] 한 값이랑 둘 중에 min값을 dp[i]에 저장하면 된다. 3도 동일하다.

 

dp 테이블을 미리 만들어 놓고 append가 아닌 그냥 =연산자로 사용했다. 1000001인 이유는 dp[1] 을 1로 생각하기 위해서다. dp[1000001]은 1,000,000번째 이기 때문. (N <= 1,000,000)

 

나의 코드

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

print(dp[N])