(DP)を白準1463号1にする
5823 ワード
解読を始めたばかりのコードです。
n = 10
count = 0
def solution(i):
global count
if i <= 1:
return False
count += 1
if i > 3:
if i % 3 != 0:
solution(i-1)
else:
solution(i//3)
else:
return
solution(n)
print(count)
私のようにコードを書くのはDPを間違えたことです.DPは点火式のように、最初から数を求めて入れてみましょう.リファレンス
正しいコード
n = int(input())
dp = [0] * (n+1) # 메모이제이션, 값을 기록하기 위한 공간
for i in range(2, n+1): # 어차피 1은 자기 자신이므로 2부터 시작
dp[i] = dp[i-1] + 1 # 현재 값은 전 값의 +1이다. (마지막 조건에서 1을 빼기 때문에)
# 다만 2와 3으로 나누어 떨어질 경우에는 2와 3으로 나눈 값, 즉 전 값에다가 1을 더한 값 (전 값이므로)과 기존에 정의했던 값과 비교해서 작은 값을 정답으로 한다.
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2]+1)
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
print(dp[n])
Reference
この問題について((DP)を白準1463号1にする), 我々は、より多くの情報をここで見つけました https://velog.io/@jwun95/DP-백준-1463번-1로-만들기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol