[baekjoon] 백준 1463번 : 1로 만들기 (by python) dp

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

정답 code

n = int(input())

dp = [0] * (n+1) #0부터 x까지 연산횟수 저장

for i in range(2,n+1):
    dp[i] = dp[i-1]+1 # 2,3으로 나누어지지 않을경우 전 수의 경우의수 +1 문제조건 3경우


    if i % 2 == 0: #문제조건 2의 경우: 앞서 저장했던 3조건과 비교후 더 작은수 저장
        dp[i] = min(dp[i],dp[i//2]+1)
    if i % 3 == 0: #문제조건 1의 경우: 앞서 저장했던 3,2조건중에 더작은수와 비교후 저장
        dp[i] = min(dp[i],dp[i//3]+1)

print(dp[n])

 

이 문제를 처음 봤을땐 쉽다 생각했지만 예제를 보고 다른 경우의 수가 여럿 잇는걸 확인 후에는 어떻게 풀어야 할지 고민을 했다.

 

solution

결국은 아래서부터 순차적으로 연산횟수를 계산해 올라가는 방법을 사용하였다.

1일때를 구하는거니 1이면 연산횟수가 0

2이면 -1 을하거나 //2를 하는경우 연산횟수 1 

3이면 최솟값(1을빼서 2의 경우의수연산횟수(1)에 +1 =  2 , 3으로 나누는 연산횟수 1) = 1

4이면 최솟값( 1을빼서 3인경우의 연산횟수(1)에 +1 =2 , 2로나누어 2인경우 연산횟수에 +1 = 2) = 2

5이면 최솟값(1을빼서 4인경우의 연산횟수(2)에 +1 = 3,조건해당없음) = 3

6이면 최솟값(1을빼서 5인경우의 연산횟수(3)에 +1 = 4 , 3으로 나누어 2인경우연산횟수(1)에 +1 = 2, 2로나누어 3인경우 연산횟수(1)에 +1 = 2) = 2

.

.

.

 

이런식으로 조건에 맞추어 주어진 n까지 최소 연산횟수의 값을 찾아 나가는 방법을 사용하였다.

 

주의 해야할점은 2로나누는경우 와 3으로 나누는경우를 둘다 if 로 처리해 둘다 실행되도록 처리해야한다.