[백준1463번][백준][baekjoon][1463번][DynamicProgramming][DP][1로 만들기][Python][파이썬]

문제링크

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

1463번: 1로 만들기

 

문제

 

풀이

가장 기본적인 DP 문제입니다. 조건 3가지 (1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을뺀다) 를 사용해서 1을 만들기 위한 가장 적은 연산 횟수를 찾는 문제입니다. bottom-up(반복)을 통해서 문제를 풀었습니다. DP의 기본인 점화식을 세우면 아래와 같이 나타낼 수 있습니다.

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.         -> D[N] = D[N/3]+1

2. X가 2로 나누어 떨어지면, 2로 나눈다.               -> D[N] = D[N/2]+1

3. 1을 뺀다.                                                    -> D[N] = D[N-1]+1

 

제가 선택한 bottom-up 방식은 작은 문제부터 시작해서 점차 큰 문제로 확장해가는 방식입니다.

숫자 1은 0번의 연산이 필요

숫자 2는 1번의 연산이 필요(2/2)

숫자 3은 1번의 연산이 필요(3/3)

숫자 4는 2번의 연산이 필요 (4/2/2 또는 (4-1)/3)

숫자 5는 3번의 연산이 필요 ( 숫자 5는 -1 조건의 연산만 가능하며 숫자 4가 되고, 숫자 4는 최소 2번의 연산이 필요)

숫자 6은 3번의 연산이 필요 ( 숫자 6은 6/2=3 또는 6/3=2 이 가능하며, 결과인 숫자 2와 숫자 3 중 적은 연산이 필요했던 숫자보다 하나의 연산이 더 필요합니다.)

 

위의 과정을 반복하면 원하는 숫자의 최소 연산 횟수를 구할 수 있습니다.

 

코드

#Python

testcase=int(input())
 
dp=[ 0 for _ in range(testcase+2) ]
dp[2]=1
 
for i in range(2, len(dp)):
 
    dp[i]=dp[i-1]+1
 
    if i%3==0:
        if dp[i]> dp[int(i/3)]+1:
            dp[i]=dp[int(i/3)]+1
    if i%2==0:
        if dp[i]> dp[int(i/2)]+1:
            dp[i] =dp[int(i/2)]+1
 
print(dp[testcase])
 
 

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

이번 포스팅에서는 python으로 작성하였지만, 추후 C와 C++ 코드도 올리도록 하겠습니다.