[Baekjoon]백준 1463 1로 만들기(실버 3) - Python

문제를 살펴보면 3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우 3가지를 통해 입력받은 수를

1로 만들어야하는데, 연산하는 횟수의 최솟값을 찾아야한다

문제의 조건을 보니 당연하게도 일반적인 if문을 나열하여 수를 계산하면 최솟값이 아닌 경우가 출력되는

경우가 많을것같다는 생각이 들었다

예제에서도 볼 수 있듯이 10인 경우 -1을 하는 조건을 둘 다 안 나누어질때로 설정해버리면

10 5 4 2 1의 과정으로 총 4번의 과정을 통해 1을 만들기때문이다

 

그래서 Dynamic Programming을 활용하여 횟수를 저장하는 딕셔너리를 만들고 호출하도록 작성해보았다

num = int(input())
result = {1:0}

def sol(n):
    if n in result.keys():
        return result[n]
    if n % 3 == 0 and n % 2 == 0:
        result[n] = min(sol(n//3) + 1, sol(n//2) + 1)
    elif n % 3 == 0:
        result[n] = min(sol(n//3) + 1, sol(n-1) + 1)
    elif n % 2 == 0:
        result[n] = min(sol(n//2) + 1, sol(n-1) + 1)
    else:
        result[n] = sol(n-1) + 1
    return result[n]

print(sol(num))

sol함수에 n이라는 인자를 입력받는다 result 딕셔너리를 확인하여 이미 key값이 존재한다면 해당 값을 반환하면 된다

3과 2로 둘 다 나누어진다면 n//3의 경우와 n//2 경우 두 가지로 나누어 더 최솟값을 result[n]에 저장해준다

그 나머지도 동일하게 3으로 나누어진다면 n//3의 경우와 1을 빼는 경우,

2로 나누어진다면 n//2의 경우와 1을 빼는 경우 두가지로 나누어 최솟값을 result[n]에 저장한다

그리고 해당 함수는 result[n]을 반환하면 해당 코드는 완성이다

 

찾아보니 해당 방법 말고 BottomUp방식도 존재한다

num = int(input())
result = [0] * (num + 1)

for i in range(2, num + 1):
    result[i] = result[i-1] + 1
    if i % 2 == 0:
        result[i] = min(result[i], result[i//2] + 1)
    if i % 3 == 0:
        result[i] = min(result[i], result[i//3] + 1)
        
print(result[num])

이 방법은 result[num]이 될때까지의 최솟값을 더해가는 과정인데, 시작을 1부터 하기 때문에 BottomUp방식이다

result[1]은 1이기 때문에 0이 저장되어있을거고, result[2]는 2에서 1을 빼거나 2를 나누면 1이 되기 때문에 2가 저장된다

이러한 과정을 계속해서 반복해나가면서 2로 나눈경우, 3으로 나눈경우, -1을 한 경우의 최솟값을 구하여

result 배열을 채워나가게 되고, 이를 통해 결과값을 출력할 수 있다