문제

문제 링크

코드

DFS

import sys
sys.setrecursionlimit(10**8)

cache = dict()
def dp(x, y, n, count):
    if (x,y,n, count) in cache.keys():
        return cache[(x,y,n, count)]
    elif  x == y:
        # print(f"catch! {x} {y} {n} {count}")
        cache[(x,y,n, count)] = count
        return count
    elif x > y:
        return 1000001
    else:
        # print(f"{x} {y} {n} {count}")
        return min(dp(x+n, y, n, count+1),dp(x*2, y, n, count + 1),dp(x*3, y, n, count+1)) 

문제점

recursion depth limit에 걸려서 런타임 에러가 발생했다.
그리고 시간 초과가 발생한다.
사실 로직이 맞는데도 시간 초과가 발생했다면 무조건 dp를 써야 하지만 위의 코드는 제대로 dp를 쓸 수 없는 문제였다. 왜냐면 dp를 쓸려면 적어도 분할 정복이 가능해야 하는데, 위의 점화식으로는 적절하게 분할 정복이 안되기 때문이다.

분할 정복 : 같은 형태의 문제로 하나의 문제가 여러 개로 쪼개지는 것

BFS

from collections import deque

def solution1(x, y, n):
    # (x, y, n) = (1,1000000,1)
    # b2, b3 = y//2, y//3
    q = deque()
    q.append((x,0))
    while q:
        now, count = q.popleft()
        if now == y:
            return count
        elif now > y:
            continue
        q.append((now+n,count+1))
        q.append((now*2, count+1))
        q.append((now*3,count+1))
    return -1

문제점

시간 초과가 났다. 사실 로직은 무조건 맞다. 틀릴 수 없는데 시간 초과가 났다는 것은 어떤 곳에서든지 최적화가 일어나야 하는데, 이럴 땐 무조건 dp라 생각한다.
그래서 dp로 풀어야 한다는 것을 느낄 수 있었다. 그러나 방법을 찾지 못했다.

DP

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

분석

분할 정복이 가능했나?

# 분할 정복된 코드
if i + n <= y:
    DP[i+n] = min(DP[i] + 1, DP[i+n])
if i * 2 <= y:
    DP[i*2] = min(DP[i] + 1, DP[i*2])
if i * 3 <= y:
    DP[i*3] = min(DP[i] + 1, DP[i*3])

여기선 문제가 점화식 관계로 쪼개지진 않았다. 그러나 분할 정복이 가능했다. 왜냐하면 모든 문제가 if문 안에 있는 코드처럼 쪼개졌기 때문이다. 이런 식의 접근도 있다는 것을 기억해두는 수 밖에 없을 듯 하다. 암기하자!

DP 유형

1. cache 처럼 dp를 사용
   • 팩토리얼(재귀함수 사용 시)
2. 배열을 이용하여 dp 사용
   • x에서 y까지 가는 방법 중에 최소 연산
   • 2xN 타일