[백준] 1463번 : 1로 만들기

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

1463번: 1로 만들기

문제 : 나누기 3과 나누기2와 빼기의 세개의 연산을 적절히 사용하여 1을 만드는데 횟수의 최소값을 구해야한다.

 

테스트 케이스

입력 10이고 출력이 3일때 10->9->3->1 로 3번 만에 만들 수 있다.

 

 dp 테이블을 입력의 개수만큼 생성한다. 

dp[10] = 0 # 연산X

dp[9] = 1  # -1

dp[8] = 2 # -1 -1

dp[7] = 3 # -1 -1 -1

dp[6] = 4 # -1 -1 -1

dp[5] = 1 # 나누기 2

dp[4] = 2 # 나누기2, -1 

dp[3] = 2 # -1, 나누기3

dp[2] = 3 # 나누기3, -1

dp[1] = 3 # 나누기3, 나누기3, -1

 

점화식 도출 ( 탑 다운 방식 )

dp[1] = min(dp[3] +1, dp[4]+1, dp[2]+1)

dp[2] = min(dp[6] + 1, dp[4]+1, dp[3]+1)

dp[3] = min(dp[9] +1, dp[6]+1, dp[4]+1)

dp[4] = min(dp[8]+1, dp[5]+1)

dp[5] = min(dp[10]+1, dp[6]+1)

dp[6] = min(dp[7]+1)

dp[7] = min(dp[8]+1)

dp[8] = min(dp[9] +1)

dp[9] = min(dp[10]+1)

dp[10] = 0

 

X = int(input())
INF = int(10e9)
dp = [INF for _ in range(X+1)] # X+1 크기만큼의 배열을 생성


def makeNumber1(number):
    if number >= X:
        return 0

    if X >= number * 3:
        dp[number*3] = makeNumber1(number*3)
        dp[number] = min(dp[number*3]+1, dp[number])
    if X >= number * 2:
        dp[number*2] = makeNumber1(number*2)
        dp[number] = min(dp[number*2]+1, dp[number])
    if X >= number + 1:
        dp[number+1] = makeNumber1(number+1)
        dp[number] = min(dp[number+1]+1, dp[number])
    
    return dp[number]
    
result = makeNumber1(1)
if result == INF:
    print(0)
else:
    print(result)

 

바톰업 방식으로 문제를 바꿔서 풀면 아래와 같이 점화식을 나타 낼 수 있다.

dp[1] = 0

dp[2] = dp[1] + 1

dp[3] = min(dp[1] +1, dp[2] +1)

dp[4] = min(dp[2]+1, dp[3] +1)

dp[5] = dp[4]+1

dp[6] = min(dp[3]+1, dp[2]+1, dp[5]+1)

dp[7] = dp[6]+1

dp[8] = min(dp[4]+1, dp[7]+1)

dp[9] = min(dp[3]+1, dp[8]+1)

dp[10] = min(dp[9]+1, dp[5]+1)

 

dp[6]을 구하는 과정을 보면 3으로 나눌수있으면 dp[3]에서의 +1값, 2로 나눌수 있으면 dp[4]에서의 +1값 , dp[5]에서의 +1값을 구한다. 3에서 온경우, 4에서 온경우 5에서 온경우에서의 최소값을 구한다. 이미 dp[3], dp[4], dp[5]는 각각의 자리에서의 최소값을 가지고 있다.

 

N = int(input())

dp = [0] * int(N+1)

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])
        
    if i % 6 == 0:
        dp[i] = min(dp[i], dp[i//3]+1, dp[i//2]+1)
    
print(dp[N])

다음과같이 코드로 구현 할 수 있다.