[BOJ:1463] 1로 만들기

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

Note

문제풀이과정 회고

처음에는 정수 별 특징으로 수를 분류가 가능할 것으로 생각하였다. 예를 들면 2의 배수, 3의 배수, 혹은 3의 배수가 아닌 홀수로 분류하고, 문제에 주어진 대로 짝수라면 2로 나누고 홀수라면 3으로 나누어 떨어지는지 확인하고 나누어 떨어지면 나누고, 아니라면 -1을 하는 식으로 연산을 수행해보았다. 하지만 이 방식에서는 예외 사항들이 많았다. 예를 들면 10의 경우 짝수이기 때문에 처음에 2로 나누어 진행하면 5가 된다. 그리고 그 다음 과정을 진행하면 다음과 같다. '10 -> 5 -> 4 -> 2 -> 1' 하지만 이 방식은 최소 연산 사용이 아니다. '10 -> 9 -> 3 -> 1'이라는 더 최소 연산 진행 방법이 존재한다.
그래서 추가 조건들을 더 생각하여 짝수지만 -1을 했을 때 3의 배수인 수일 경우의 연산 방법 등도 생각해보았지만 경우를 분류할 때마다 새로운 예외 정수들이 생겨났다. 모든 수에 대하여 예외 조건을 분류하기 어려울 것이라고 생각하였고, 관점을 전환 했다. 주어진 수에서 연산하는 것이 아닌 1에서 주어진 수로 최소 연산으로 가는 방식을 생각해보았다. 이때 는 '/2', '/3', '-1' 연산이 아니라 역 연산 '*2', '*3', '+1'로 진행하여 입력으로 주어진 수에 최소 연산을 수행하여 도달 하는 방식을 계산했다. 하나씩 적음면서 계산을 해보니 규칙이 보였다.
min_dis[i]는 i까지 오는 최소 연산(경로로 생각하여 min_distance라는 의미로 min_dis라고 변수명 명명) 초기항은 min[1] = 0, min_dis[2] = 1, min_dis[3] = 1을 설정하고 다음 수들의 연산 횟수를 계산했다. 4는 앞의 정수 2의 2배를 하여 도달 가능하므로  min_dis[2] + 1이 min_dis[4]의 값이다. 5는 '*'연산을 통해 도달 할 수 없으므로 4까지 온 다음 +1을 하여 도달해야한다. 6은 2의 3배 또는 3의 2배이므로 2까지의 경로, 3까지의 경로의 최솟값을 구하고 그 최소값의 +1을 하여 구할 수 있다. 7은 5의 경우와 마찬가지로 '*'를 통해 도달 할 수 없으므로 직전 까지 수의 +1을 통해 도달 가능하다. 이런식으로 구하다 보면 10을 만나게 되는데 10은 5의 2배를 통해 도달 할 수 있다. 그렇다면 min_dis[10]은 min_dis[5](3) +1로 4가 될 것 같지만 이보다 더 빠른 경로가 존재한다. min_dis[9](2) + 1을 통해서도 도달이 가능하다.  이 경우는 3으로 4보다 작다.

정리하면 어떤 숫자 n에 최소로 도달하기 위해서는 *연산을 하면 빨리 도달이 가능하므로 *연산을 통해 도달이 가능한지 확인해본다. 하지만 n-1까지 도달하는 경로 +1이 더 작다면 이 경우가 최소 경로이다.

Code

import sys
input = sys.stdin.readline
n = int(input())
cnt = 0
min_dis = [float("inf") for _ in range(n+1)]
min_dis[1] = 0
if n == 2:
    min_dis[2] = 1
elif n >= 3 and n <4:
    min_dis[2] = 1
    min_dis[3] = 1
elif n >= 4:
    min_dis[2] = 1
    min_dis[3] = 1
    min_dis[4] = 2

for num in range(5,n+1):
    if num % 6 == 0:
        min_val = min(min_dis[num//2],min_dis[num//3],min_dis[num-1])
        min_dis[num] = min_val + 1
    elif num % 3 == 0:
        min_val = min(min_dis[num//3],min_dis[num-1])
        min_dis[num] = min_val + 1
    elif num % 2 == 0:
        min_val = min(min_dis[num//2],min_dis[num-1])
        min_dis[num] = min_val + 1
    else:
        min_dis[num] = min_dis[num-1] + 1

print(min_dis[n])