BAEKJOON : 1463, 11005

No. 1463

1. Problem

2. My Solution

動的計画Top-Down

n,

Pythonは、再帰関数の回数がデフォルトの制限より大きい場合、ランタイムエラー(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

ダイナミックプログラミングについて
-最適な局所構造を有する問題を解決する際に、同じ値の再帰的

を繰り返すことを避ける.
リストではなくdictを使用して

DPを実装したほうが良いかもしれません

Pythonで無限大を表現するために、math.inf

を使用

No. 11005

1. Problem

2. My Solution
整数

2を求める原理に沿って、b進法

のみを変更する.

10の場合、「A」を表すために残りの(j)に+55を加え、Askyコードを文字

に変換する

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は、どのような方法で出力に変換するか考えてみましょう.