[코테] 동적 프로그래밍 - 1로 만들기

문제 설명

동적 프로그래밍(이하 DP)을 처음 접했을 때는 백트래킹(이하 BT)이랑 다른게 뭐지 싶었다.

정확히 말하자면, DP와 BT 관련 문제를 봤을때 대체 어떤게 DP로 풀어야 효율적이고 BT로 풀어야 효율적인지 판단이 되지 않았다.

 

예를 들어, 제일 애먹었던 N-queen 문제를 나도 모르게 DP로 구현했지만 (DP가 뭔지 몰랐을 때 였다..) 자꾸 시간초과가 떴다. 고수님들한테 물어보니 BT로 풀어야하는 문제더라.

 

그 후에 DP를 공부하고 문제를 풀면서 생긴 DP, BT 구별법은 다음과 같았다.

 

Q1. 문제를 점화식으로 정의할 수 있는가?

Q2. 백트래킹으로 구현하려할때, 불필요한 중복계산이 많이 발생하는가?

 

Q1과 Q2의 대답이 YES일때 DP로 풀어야겠다고 생각한다.

"1로 만들기" 문제의 경우 Q2에서 YES라고 생각했으므로 DP로 풀게 되었다. (Q1은 좀 어렵..)

3으로 나누기, 2로 나누기, 1을 빼기 연산을 어떤 순서로 사용했을 때 최소한의 연산으로 1이 되는가.. 에 대해 고민하다가

 

어찌됐든 간에 주어진 N부터 1까지 모든 수에 대해서 최소 연산 수가 존재하기 때문에 

N부터 1까지의 모든 수의 최소 연산수를 차례대로 구해보자!

로 문제 풀이 방향을 정했다.

 

N= int(input())
d= [N-i for i in range(N+1)]
for i in range(N, 0, -1):
    memo = d[i] + 1
    if i%3 == 0 and d[i//3] > memo:
        d[i//3] = memo
    if i%2 == 0 and d[i//2] > memo: 
        d[i//2] = memo
    if d[i-1] >= d[i] and d[i-1] > memo:
        d[i-1] = memo
print(d[1]) if N >1 else print(0)

N부터 1씩 내려오면서 최소 연산 수를 구하는 코드이다.

문제 풀이에 성공했지만 생각보다 시간이 너무 오래걸리더라.. (약 700ms) 

1위가 36ms 길래 헉 하면서 코드를 보곤 감탄했다...

 

from sys import stdin

d = {1: 0, 2: 1}


def sol(n: int) -> int:
    print(n, d)
    if n in d:
        return d[n]
    t = 1 + min(sol(n // 3) + n % 3, sol(n // 2) + n % 2)
    d[n] = t
    
    return t


print(sol(int(input())))

이분 코드 뿐만 아니라 DP문제들을 풀고 나서 상위권 유저들의 코드들을 참고했을때 느꼈던건

초기 값을 주고 수열 문제 풀듯이 푸는 방법이 굉장히 많았다는 것

 

아직 탑-다운인지, 바텀-업인지 잘 모르는 레벨이라 구분은 못하겠지만 위와 같은 방식으로 푸는 연습도 꾸준히 해야겠다.

이번 주 안에 골드 가야지 ^____^