BAEKJOON : 1463, 11005

No. 1463

1. Problem

2. My Solution

• Dynamic Programming Top-Down 방식
• n 보다 더 작은 (이전) 값의 결과를 이용함
• 파이썬은 재귀함수의 횟수가 기본적으로 제한된 횟수 보다 많으면 런타임 에러 (RecursionError)

import sys
import math

def solution(n):
    if dp[n] >= 0:
        return dp[n]
    else:
        a = b = c = math.inf

        if n % 3 == 0:
            a = solution(n//3) + 1
        if n % 2 == 0:
            b = solution(n//2) + 1
     
        c = solution(n-1) + 1	# 이 부분에서 과도한 recursion 발생
        
        dp[n] = min(a,b,c)
        return dp[n]
        

dp = [0,0,1,1,2] + [-1] * 999996
n = int(sys.stdin.readline().rstrip())
print(solution(n))

3. Others' Solutions

• Top-Down 방식
• DP 구현을 위해서 dict 자료형 사용
• Devidedp(testNum-1) 재귀 부분이 위에처럼 모두 수행되지 않음

testNum = int(input())

dp = {} 	# dict 사용 
dp[1] = 0

def Devidedp(testNum):
    if testNum in dp:
        return dp[testNum]
        
    if(testNum%3 == 0 and testNum%2 == 0):
        dp[testNum] = min(Devidedp(testNum//2),Devidedp(testNum//3))+1
        
    elif(testNum%3 == 0):
        dp[testNum] = min(Devidedp(testNum-1),Devidedp(testNum//3))+1
        
    elif(testNum%2 == 0):
        dp[testNum] = min(Devidedp(testNum-1),Devidedp(testNum//2))+1
        
    else:
        dp[testNum] = Devidedp(testNum-1)+1
    return dp[testNum]



print(Devidedp(testNum))

• Bottm-Up 방식

import sys
import math

dp = {}
dp[0] = 0
dp[1] = 0
n = int(sys.stdin.readline().rstrip())

for i in range(2,n+1):

    a = b = c = math.inf
    if i % 3 == 0:
        a = dp[i//3] + 1
    if i % 2 == 0:
        b = dp[i//2] + 1
    c = dp[i-1] + 1

    dp[i] = min(a,b,c)

print(dp[n])

4. Learned

• Dynamic Programming 에 대해서 알게됨
  - 최적 부분 구조를 갖는 문제를 해결할 때, 같은 값의 재귀함수가 중복되어 실행되는 것을 방지
• DP 구현을 위해 리스트가 아닌 dict 를 이용하면 더 좋을 것 같음
• 파이썬에서 무한대를 표현하기 위해선 math.inf 사용

---

No. 11005

1. Problem

2. My Solution

• 2진수를 구하는 원리를 그대로 사용하여 b 진법만 변경
• 10 일때 'A' 를 나타내기 위해서 나머지(j)에 + 55를 한뒤 아스키 코드를 문자로 변환

import sys

n,b = map(int,sys.stdin.readline().rstrip().split())
result =''

while(True):
    
    i,j = divmod(n,b)

    if n == 0:
        break
    if j >= 10:
        result += chr(j+55)
    else:
        result += str(j)
    n = i

result = result[::-1]
print(result)

3. Learned

• 10 -> A 이런식으로 치환하여 출력하기 위해서 어떤 방법을 쓸지 생각해보자