[백준/Python] 1463. 1로 만들기

📌 문제 유형: DP

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

 

 

📌 풀이

 

문제를 읽으면서 딱 눈에 들어오는 것은, 시간 제한이 0.15초 밖에 안된다는 점이다. 

그리고 N이 1~10^6이라면, 완전탐색으로는 시간 초과가 날 것이라는 걸 느끼게 된다. 

 

이 상태에서 문제를 좀 더 살펴보자. 

 

3으로 나누어 떨어질 때, 2로 나누어 떨어질 때, 둘 다 아닐때 이렇게 3가지 경우에 대해 연산을 제한해 두고 있다. 이 3개의 연산을 적절히 사용해 연산 횟수를 MIN로 만드려고 한다.

 

드는 생각들! 

1. 3의 배수일 때 (2의 배수는 아님)

2. 2의 배수일 때 (3의 배수는 아님) 

3. 둘 다 아닐 때 - 1을 뺀다. 

4. 6의 배수일 때 ==> 이 경우가 추가되어 고려될 수 있다. 

 

이때 연산 횟수가 MIN이 되려면, 나누었을 때 몫이 작을수록 좋다는 생각이 들 것이다. 

 

즉 위의 4가지 경우에 대해서, 아래처럼 생각해볼 수 있다.

 

1. 6의 배수일 때 => 2 또는 3으로 나누면 된다. 굳이 1을 뺄 필요가 X 
==> N = MIN(3으로 나누었을 때 몫, 2로 나누었을 때 몫) 을 N으로 다시 둔다. 

2. 3의 배수일 때 => 3으로 나누거나, 1을 빼거나 2가지 선택지가 있다. 
==> N = MIN(3으로 나누었을 때 몫, 1을 뺀 값) 

3. 2의 배수일 때 => 2로 나누거나, 1을 빼거나 2가지 선택지가 있다. 
==> N = MIN(2로 나누었을 때 몫, 1을 뺀 값) 

4. 위의 경우가 모두 해당되지 않아, 1을 무조건 빼야 하는 경우 
==> N = N - 1

 

이 내용을 재귀 함수로 만든다.

 

이때 메모제이션, 즉 cache를 선언해 이미 계산한 값은 저장해 두었다가, 나중에 다시 필요할 때 불러와 쓸 수 있도록 한다. 

 

이것을 코드로 나타내면 아래와 같다. 

 

import sys

N = int(input())
sys.setrecursionlimit(10**6)
INF = 987654321
cache = [INF] * (N+1)
cache[1] = 0

def dp(n):
    if cache[n] != INF:
        return cache[n]
    if n%6 == 0:
        cache[n] = min(dp(n//3), dp(n//2)) + 1
    elif n%3 == 0:
        cache[n] = min(dp(n//3), dp(n-1))  + 1
    elif n%2 == 0:
        cache[n] = min(dp(n//2), dp(n-1)) + 1
    else:
        cache[n] = dp(n-1) + 1
    return cache[n]

print(dp(N))