[백준] - 1463. 1로 만들기(python)

[top down 방식과 memoization]

import sys
sys.setrecursionlimit(10**6)
def dp(n):
	#base case
    if n == 2 or n == 3:
        memo[n] = 1
        return memo[n]
    elif n == 1:
        memo[n] = 0
        return memo[n]
        
       
    #memoization
    if n not in memo:
        if n % 6 == 0:
        	#점화식
            memo[n] = 1+min(dp(n//3),dp(n//2))
            
        elif n%3 == 0:
        	#점화식
            memo[n] = 1+min(dp(n//3), dp(n-1))
            
        elif n%2 == 0:
        	#점화식
            memo[n] = 1+min(dp(n//2), dp(n-1))
        else:
        	#점화식
            memo[n] = dp(n-1)+1
    return memo[n]
        

    
memo = {}
n = int(input())
print(dp(n))

Base case

• 1에서 1이 되는 최소 연산수 - 0번
• 2에서 1이 되는 최소 연산수 - 1번 (방법은 두개지만 둘다 연산은 1번만 하면 됨) 
  • 2 - 1 = 1
  • 2 // 2 = 1
• 3에서 1이 되는 최소 연산수 - 1번
  • 3//3 = 1

memoization

• 해당 문제는 중복되는 결과값이 있기 때문에 이를 계속해서 매번 중복 계산해주는 일은 시간 복잡도에 큰 영향을 미칠 것이다.
• 그렇기 때문에 이미 한 번 해결한 문제라면 해당 로직을 실행하지 않고 memoization(array(파이썬에선 리스트), hash table(파이썬에선 딕셔너리))에 저장 해둔 계산 값을 가져와서 사용하기만 해보자.

점화식

0	1	1
1	2	3	4	5	6	7	8	9	10

•  3과 2로 나눠지는 경우 = 최소 공배수 6을 사용해서 진행
  • 6의 경우엔 3과 2모두 나눌 수 있어서 이 두가지를 비교해주면 된다. 
• 3으로 나눠지는 경우
  • 3으로 나눴을 때 횟수와 1을 뺏을때 횟수를 비교해서 덜 조금 사용된 것을 가져오도록
• 2로 나눠지는 경우
  • 2로 나눴을 때 횟수와 1을 뺏을 때 횟수를 비교해서 조금 덜 사용된 것을 가져오도록
• 어떠한 수로도 나눠지지 않는 경우엔 1을 뺀 수를 보아야 한다.

핵심

• top - down 방식으로 Memoization과 함께 문제를 풀었다.
  • 재귀를 사용하여 문제를 풀때 문제 풀이는 쉬워지지만 해당 문제의 runtime error를 고려해야 한다.
  • 해당 문제를 해결하기 위해서 import sys / sys.setrecursionlimit(10**6)라는 제한을 둬서 해당 재귀가 제한된 깊이까지만 들어갈 수 있도록 설정했다.

위에서 아래로 가는 문제로 아래 표와 함께 이해해보자

10의 최소 연산수를 구한다고 할때

1. 초기 base case만 두었을 때 

memo = {}

0	1	1
1	2	3	4	5	6	7	8	9	10

---

2. 10은 2로 나눠진다. 

    - 이때 3으로 나눠지는 것은 고려하지 않아도 된다. (나눠지지 않으니까 ;; 펀쿨섹 같은 느낌)

    - 10을 2로 나누는 경우와 1을 뺏을 경우와 비교해서 더 적은 연산을 하는 것을 택할 수 있게 한다.

    - top down 방식은 위에서 아래로 문제를 해결해나가기 때문에 당장에는 9나 5중에 어떤 수가 더 최소 연산을 하고 있는지 모른다. 그렇기 때문에 재귀를 통해서 풀이하는 것이고 재귀가 모두 끝나면 결과값이 나올 것

0	1	1		아직 모름				아직 모름
1	2	3	4	5	6	7	8	9	10

 

3. 5는 2와 3중 어떤 수로도 나눠지지 않는다.

   - 나눠지지 않는다면 둘다 고려하지 않아도 된다.

  - 1을 뺏을 경우만 고려해준다.

0	1	1	아직 모름	memo[4] + 1
1	2	3	4	5	6	7	8	9	10

 

4. 4는 2로 나눠진다.

    - 2로 나눴을 때와 해당 값에 -1 했을 경우를 고려한다.

0	1	1	2
1	2	3	4	5	6	7	8	9	10

• 2와 3 어떤 수를 골라도 최소 연산은 4의 최소 연산은 2가 된다.
  • 2로 나눌 경우 -  4 -> 2 -> 1
  • -1할 경우 - 4 -> 3 -> 1

 

5. 다시 3으로 가면 결과적으로 5의 최소 연산 횟수는 2로 저장된다.

0	1	1	2	3
1	2	3	4	5	6	7	8	9	10

 

6. 9는 3으로 나눠진다.

    - 이때 2로 나눠지는 것은 고려하지 않아도 된다.

   - 9를 3으로 나누는 것과 9에서 1을 뺀 것을 고려해서 최소 연산을 택할 수 있게 한다.

0	1	1	2	3			아직 모름	min(memo[3] + 1, memo[8]+1)
1	2	3	4	5	6	7	8	9	10

 

7. 8은 2로 나눠진다.

   - 2로 나누는 것과 해당 값에서 1을 빼는 것을 고려한다.

0	1	1	2	3		아직 모름	min(2, memo[7]) +1	min(memo[3] + 1, memo[8]+1)
1	2	3	4	5	6	7	8	9	10

 

8. 위의 과정을 반복하면 결과적으로 10의 최소 연산은 3이라는 수가 나온다.