백준 1463번 1로 만들기

전형적인 DP문제로 10 -> 1로 만드는 것 보다 1 -> 10을 가면서 최단거리를 찾는 방법으로 문제를 해결할 수 있다.  

힌트의 나와있는 10의 경우를 예로 들면 1 -> 10까지 가는 최단 방법을 배열로 구하는 것이다.

이때 10 -> 1로 가는 경우를 예로 들어보자

고려해야할 조건은 다음과 같다

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

2. X가 2로 나누어 떨어지면, 2로 나눈다

3. 1을 뺀다

1 -> 10을 가기 위해 1부터 2, 3 차근차근 진행해 나가보자

1 -> 2를 가기 위해선 3번 조건을 통해 1을 더해 갈 수 있다. 즉, DP배열을 사용하면

[0,0,1]이 되는것이다.(index의 편의를 위해 0번째 index에는 0을 추가해주었다.)

 

이때 1은 1에 1을 더하는 연산을 한 번 수행하여 갈 수 있으므로 1이라고 표현된다.

이후 2는 2로 나누어 떨어지기에 min(DP[1], DP[2/2]+1)을 계산해준다. 결과값은 동일하게 1이 된다.

다음으로 2->3으로 가는 경우를 확인해보자.

1에서 2까지 오는 최단 경로는 1이므로, 3이 되기 위해선 2에서 +1을 한번 더 해주어 2가 된다.

따라서 DP배열은 다음과 같이 형성된다

 

[0,0,1,2]

 

그러나 여기서 3은 3으로 나누어떨어지는 1번 조건을 만족하기에 다음과 같은 계산을 해준다

min(DP[2]+1, DP[3/3]+1) = 1

즉, 3을 3으로 나누면 바로 1이 되므로, 1에서 바로 3을 곱해주는 연산을 통해 3으로 올 수 있는 것이다.

즉 1까지의 최단거리 + 1번의 연산 만으로 3에 도달하게 되므로 배열은 다음과 같이 변화한다.

 

[0,0,1,2] -> [0,0,1,1]

 

이러한 식으로 원하는 숫자에 진행될 때 까지 DP배열을 생성하여 최단거리를 계산하면 답이 나오게 되는 문제이다.

이를 특정값 X에 대해 구해보면 다음과 같은 식이 나온다

 

DP[X] = DP[X-1]+1

만약 X가 3의 배수라면 -> DP[X] = min(DP[X-1]+1, DP[X/3]+1)

만약 X가 2의 배수라면 -> DP[X] = min(DP[X-1]+1, DP[X/2]+1)

 

이를 코드로 나타내면 다음과 같다.

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