백준 1463 파이썬 - 1로 만들기 - 동적 계획법

백준 1463 파이썬

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

1463번: 1로 만들기

정수 X가 주어졌을 때

• 3으로 나누어 떨어지면 3으로 나누고
• 2로 나누어 떨어지면 2로 나누고
• 그 이외는 1을 뺀다.

해당 규칙에 맞춰서 연산 횟수의 최솟값을 구하는 문제이다.

 

문제를 보고 딱 생각이 난 알고리즘이 동적 계획법이었습니다.

• 초기값으로 설정할 값이 명확했고
• 기존에 연산된 값을 재사용하는 메모이제이션이 딱 맞아 떨어졌다.

 

Python 풀이 1

import sys

read = sys.stdin.readline
N = int(read())

cache = [-1] * (N+3)
cache[1] = 0
cache[2] = cache[3] = 1

for i in range(4, N+1):
    cnt = 10**6
    if i % 3 == 0:
        cnt = min(cache[i//3], cnt)
    if i % 2 == 0:
        cnt = min(cache[i//2], cnt)
    
    cache[i] = min(cache[i-1], cnt) + 1
    
print(cache[N])

• cache는 메모이제이션을 위한 재사용 값을 저장하기 위한 용도로 사용했다.
  • cache의 크기는 N보다 3을 크게 잡았다. 1, 2가 N으로 들어올 경우 초기 값 설정할 때 Index Out if Bounds 오류를 피하기 위해서이다.
• 1,2,3 일 때 초기 값이 명확해서 설정을 먼저 진행해줬다.
• 이후 4부터 N까지 캐시값을 재사용하면서 연산을 진행한다.

전형적인 동적 계획법 문제이다.

그러나 해당 풀이로 생각보다 연산 시간이 오래결러서 다른 방법을 찾아봤다.

 

 

Python 풀이 2

풀이1보다 10배이상 빠르다. 우선 리스트형태로 N까지 모든 수를 확인하지 않고 수를 나누면서 꼭 필요한 값만 확인한다는 점에서 훨씬 빠르다. 그러나... 위의 풀이보다 이해하는데 시간이 소요된다. 개인적으로 재귀함수를 많이 어려워해서 이런 풀이를 보면 참 신기할 따름이다.

import sys
read = sys.stdin.readline

N = int(read())
cache = {1: 0, 2: 1}

def dp(n):
    if n in cache:
        return cache[n]
	
    # 핵심 코드
    cnt = 1 + min(dp(n//3) + n%3, dp(n//2) + n%2)
    cache[n] = cnt
    return cnt
    
print(dp(N))

• 리스트 대신 딕셔너리를 사용해서 값을 찾는 연산 속도를 줄일 수 있다.
• 재귀함수를 사용한다.
  • 캐시에 값이 있는경우 값을 반환하고
  • 핵심코드를 보면... 재귀함수에 각각 3과 2로 나눈 몫에 나머지를 더해서 최솟값을 구한다.

 

핵심코드 풀이

코드만 보면... 나머지값을 왜 더하는지 이해 안될 수 있다. 저도 이해하는데 시간이 오래 걸렸는데요... 나머지값을 더하는 이유는 7 이나 11 처럼 2와 3으로 나눌 수 없는 경우 무조건 1을 1번 이상 빼고 진행을 하게됩니다.

• 2로 나누려고하면 나머지가 1
• 3으로 나누려고하면 나머지가 1, 2

2와 3의 배수가 아닌 숫자의 규칙은 위와 같습니다. 그래서 이런 경우 2가지 분기를 타게 됩니다.

 

 

※ 예시 N=7 인 경우 3과 2로 나눴을 때 나머지가 모두 1

해당 경우 3이든 7이든 -1을 한번씩 연산하고 진행해야 하기 때문에 나머지 1을 더해주는 것은 쉽게 이해가 된다.

 

 

※ 예시 N=11 인 경우 3과 2로 나눴을 때 나머지가 각각 2와 1

해당 경우는 두가지 루트로 나눠서 진행하겠다고 생각하시면 될 것 같습니다.

•  -1을 두번 해서 3으로 나누려는 루트
• -1을 한번 해서 2로 나누려는 루트

그림으로 예시를 보면 아래와 같습니다.

11에서 9로 가서 3을 나누는 루트로... 2번의 -1 연산을 해야하기 때문에 나머지인 2를 더하고

11에서 10으로 가서 2로 나누는 루트로... 1번의 -1 연산을 해야하기 때문에 나머지인 1을 더하는 원리입니다.