1. DP 이것은 무엇인가 (백준 1463 파이썬)

DP : Dynamic Programming

내 머릿속에 일단 DP는 피보나치이다.

한 번 나왔던 값은 저장을 해서 다시 구하는 시간을 절약할 수 있다는 것이 핵심이다. 

• Top-down(하향식) 방식 : 내려가며 재귀
• Bottom-up(상향식) 방식 : 올라가며 반복문

나는 재귀를 처음 이해한 후에 재귀에 빠져서 하향식을 더 선호했는데, 사실 이제 다 잊어버리기도 했고(...) 문제마다 어떤 방식이 더 좋은지가 애초에 달라질 수 있는 것 같다.

 

백준 1463번 풀이를 하며 이해해보도록 노력하겠다.

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

---

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

---

접근법

1. 역시 일단 3으로 나누어지면 3으로 나누고 > 안되면 2 > 안되면 1 빼는 순서 --> 될리가 없다
2. 3으로 안나누어지는데 1 빼면 되는 경우 1 빼는 연산 먼저 하고 3으로 나누고 연산횟수는 2 더하는 ---> 왜인지 될거라고 생각했지만 될리가 없다. 애초에 1을 여러번 빼는 생각 자체를 못했음
3. DP를 사용해보자 - 하향식 방법과 상향식 방법 둘 다를 찾아보았다. (사람들은 천재임에 틀림없다..)

N = int(input())

# Top-down 재귀
def solution1(N):
    if N == 1:
        return 0
    elif N <= 3:
        return 1
    
    # 3으로 나누는 연산, 2로 나누는 연산 중에 더 적은 값으로 리턴
    # 핵심 : 나머지 연산한 값을 더해주는 것 : 배수로 만들기 위해 -1을 한 횟수
    return min(solution1(N//3) + N%3 + 1, solution1(N//2) + N%2 + 1)
    

# Bottom-up 
def solution2(N):
    # 저장할 배열
    dp = [0 for _ in range(N+1)]

    for i in range(2, N+1):
        # 기본적으로 이번 회차는 저번 회차보다 한 회 증가함
        dp[i] = dp[i-1] + 1
        
        # 이번 회차가 2로 나누어지고
        # 그 나누어진 애에서 한번 더한 게 더 적은 연산이라면 바꿈
        # 혹은 여기서 min()으로 둘 중 작은 애로 골라 넣어도 됨
        if i % 2 == 0 and dp[i] > dp[i//2] + 1:
            dp[i] = dp[i//2] + 1
        if i % 3 == 0 and dp[i] > dp[i//3] + 1:
            dp[i] = dp[i//3] + 1

    return dp[N]

print(solution1(N))
print(solution2(N))

• 재귀는 리턴만 잘 해도 반은 간다.. 
• 작은 수들이 주어진 경우 상향식으로 풀기
• 저장하는 배열이 각 숫자에 해당하는 값을 저장하는게 아니라, 회차에 따라 저장함을 기억하기