[백준] 1463번 1로 만들기 (Python 파이썬)

www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제 설명

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

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

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

---

풀이 과정

이 문제는, 전의 결과를 다음 결과에 이용하게 되는. 점화식을 활용한 DP 문제이다.

X = 10인 경우, 10 -> 9 -> 3 -> 1  과정을 거쳐 1이 되게 되는데

9의 경우에는 또, 9 -> 3 -> 1의 과정을 거치며

3의 경우에는 3 -> 1의 과정을 거친다.

 

즉, 10을 구할 때는 9의 결과를,

9를 구할 때는 3의 결과를 이용한다.

 

앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다.

 

일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하기 때문에

dp[i] = dp[i-1] + 1을 통해 횟수를 +1 추가 해준다.

그리고나서, dp[i]가 2 와 3으로 나누어 떨어지는 경우에는

1을 빼는 것 보다 나누어 떨어지는게 훨씬 이득이기 때문에

min(dp[i], dp[i//2]+1)을 통해 최소값을 선택하면 된다.

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !