DP 외않되...

문제 바로가기

왠지 DP로 풀 수 있을 것 같았다. BFS적 접근도 할 수 있지만, 한창 동적 계획법을 연습하고 있던 터라 시도해봤다.

def solution(x, y, n):
    if x == y:
        return 0
    if x > n:
        return -1
    
    ls = [0] * (y+1)
    for i in range(x, y+1):
        if i+n <= y:
            if ls[i+n]:
                ls[i+n] = min(ls[i] + 1, ls[i+n])
            else:
                ls[i+n] = ls[i] + 1
                
        if i*2 <= y: 
            if ls[i*2]:
                ls[i*2] = min(ls[i] + 1, ls[i*2])
            else:
                ls[i*2] = ls[i] + 1

        if i*3 <= y:
            if ls[i*3]:
                ls[i*3] = min(ls[i] + 1, ls[i*3])
            else:
                ls[i*3] = ls[i] + 1

    return ls[y] if ls[y] else -1

결과는 실패. x부터 y까지 모든 인덱스에 대해 위 과정을 실행하면, 0이어야 할 경우에도 ls[y]에 숫자가 들어갈 수 있다. 예를 들어 solution(17, 42, 5)을 실행하면 17에서 5씩 증가한 5가 나와야 하지만, 21에서 2를 곱해 42가 될 수 있기 때문에 2가 나온다.

백준 숨바꼭질

다른 풀이들을 살펴보니 백준 1697. 숨바꼭질과 비슷하다는 의견들이 많아 다시 살펴보게 되었다. 전에 재귀적 BFS로 풀었던 문제였다. 성능도 나쁘지 않았지만 더 빠른 코드들이 많아 몇군데 둘러봤다. 이번에 다시 보면서 숫자 변환하기 문제에 적용할 수 있는지 살펴보자.

jyl4you 님의 코드 :

import sys
def f(n, k):
    if n >= k:
        return n - k
    if k == 1:
        return 1
    if k % 2:
        return min(f(n, k+1), f(n, k-1)) + 1     
    return min(k-n, f(n, k//2)+1)

print(f(*map(int,sys.stdin.readline().split())))

메모리 약 31MB, 시간 36ms

백준은 이런 엄청난 코드들을 볼 수 있어 배우기 좋다. 프로그래머스도 성능 순, 클린 코드 순으로 정렬되어 있으면 좋겠다.

1. 재귀함수를 사용한다 : k라는 목표지점을 달성할 수 있는 이전 단계들에 대해 실행.
   • 나누어 떨어질때는 왜 k+1, k-1에 대해 실행하지 않는가?
     - k+1은 멀어지며 k-1보다 더 빠른 k//2가 있기 때문.
2. n이 k보다 같거나 큰 경우에는 뒤로 한칸씩 가야하므로 n-k를 반환한다.
3. 2번 경우를 제외하면 k가 1일 때는 n이 0인 경우밖에 없으므로 1을 리턴한다.
4. 2, 3번 경우를 제외하고 k가 2로 나누어떨어지지 않는다면, 다른 경우(여기서는 ±1)에 대해 함수를 실행했다.
5. 나누어 떨어지는 경우에 대해 k-n과 k//2에 대해 함수를 실행한 값 +1을 비교해 더 적은값을 반환한다.

적용 - 이해했는가?

잘 이해했는지 적용해보자.

"숫자 변환하기" 문제 분석

1. "숫자 변환하기"문제에서는 x에 n을 더하거나 2, 3을 곱한다는 경우의 수들이 존재한다.
2. 이 문제에서는 x를 y로 만들지 못하는 경우가 존재한다. -> 종료조건이 까다로울 수 있다. 어떻게 까다로운가?
3. 3으로 나누어떨어지지 않으면 2로 나눈 값과 n을 뺀 값에 대해 재귀하여 비교한다.
4. 2로 나누어떨어지지 않으면 3으로 나눈 값과 n을 뺀 값에 대해 재귀하여 비교한다.

구현

아래와 같이 구현했다.

from math import inf, isinf

def solution(x, y, n):
    def f(x, y, n):
        if x == y:
            return 0
        if y < x:
            return inf

        if y%3:   # y가 3으로 나누어떨어지지 않고
            if y%2:   # 2로도 나누어떨어지지 않으면
                return f(x, y-n, n) + 1
            else:   # 3으로 나누어 떨어지지 않지만 2로 나누어떨어지면
                return min(f(x, y//2, n), f(x, y-n, n)) + 1
        if y%2:   # 2로 나누어 떨어지지 않지만 3으로 나누어 떨어지면
            return min(f(x, y//3, n), f(x, y-n, n)) + 1
        
        # 2와 3으로 나누어 떨어지면
        return min(f(x, y//3, n), f(x, y//2, n), f(x, y-n, n)) + 1

    answer = f(x, y, n)
    if isinf(answer):
        return -1
    return answer

시간 초과가 많이 났다. 런타임 에러도 떴는데, import sys; sys.setrecursionlimit(10**6)을 추가하니 해결된 걸로 봐서 재귀의 깊이가 많이 깊어지는 것 같다. 백준 숨바꼭질에 비해 x, y의 크기가 열배까지 차이날 수 있기 때문인 것 같다.

분석중 깨달은 코드

문제를 잘 정리하니 문득 깨달음이 와서 동적 계획법으로 해결할 수 있었다. 아래에 코드를 남긴다.

def solution(x, y, n):
    if x == y:
        return 0
    if x > y:
        return -1
    
    ls = [0] * y + [1]
    for i in range(y, x, -1):
        if ls[i]:
            if i%2 == 0 and i//2 >= 0:
                ls[i//2] = min(ls[i]+1, ls[i//2]) if ls[i//2] else ls[i]+1
            if i%3 == 0 and i//3 >= 0:
                ls[i//3] = min(ls[i]+1, ls[i//3]) if ls[i//3] else ls[i]+1
            if i-n >= 0:
                ls[i-n] = min(ls[i]+1, ls[i-n]) if ls[i-n] else ls[i]+1
                
    return ls[x]-1 if ls[x] else -1

ls[i]가 0이 아닌 경우에 한해서만 진행해 해결했다. 반대방향으로 아래와 같은 코드도 가능하다 :

def solution(x, y, n):
    if x == y:
        return 0
    if x > y:
        return -1
    
    ls = [0] * (y+1)
    ls[x] = 1
    for i in range(x, y):
        if ls[i]:
            if i*2 <= y:
                ls[i*2] = min(ls[i]+1, ls[i*2]) if ls[i*2] else ls[i]+1
            if i*3 <= y:
                ls[i*3] = min(ls[i]+1, ls[i*3]) if ls[i*3] else ls[i]+1
            if i+n <= y:
                ls[i+n] = min(ls[i]+1, ls[i+n]) if ls[i+n] else ls[i]+1
    return ls[y]-1 if ls[y] else -1