[標準アルゴリズム]14631の使用
3992 ワード
質問する
1として作成
に近づく
動的計画法を利用する.
与えられた整数Nが1であれば、1の最小演算回数を0とする.
与えられた整数Nが2であれば、1または2から1を減算することができ、いずれの方法を用いても演算回数は1である.
与えられた整数Nが3であれば3に分けられ、最小演算回数は1となる.
この方法でずっと進行し、問題を解決することができます.
に答える
上のアプローチから、次の事実がわかります.
コード#コード#
1として作成
に近づく
動的計画法を利用する.
与えられた整数Nが1であれば、1の最小演算回数を0とする.
与えられた整数Nが2であれば、1または2から1を減算することができ、いずれの方法を用いても演算回数は1である.
与えられた整数Nが3であれば3に分けられ、最小演算回数は1となる.
この方法でずっと進行し、問題を解決することができます.
に答える
上のアプローチから、次の事実がわかります.
정수 N을 1로 만들기 위한 최소 연산횟수는 = '정수 N에 연산을 한 번 가한 결과'를 1로 만들기 위한 최소연산횟수 +1コード#コード#
n = int(input())
dp = [0 for i in range(n+1)]
#dp[i]: 정수 i에, 주어진 연산 세 개를 사용해서 1을 만들 때 최소횟수
dp[1] = 0
for i in range(2,n+1):
tmp = []
if i%2==0:
tmp.append(dp[i//2])
if i%3==0:
tmp.append(dp[i//3])
tmp.append(dp[i-1])
dp[i] = min(tmp)+1
print(dp[-1]) Reference
この問題について([標準アルゴリズム]14631の使用), 我々は、より多くの情報をここで見つけました https://velog.io/@syhwang4223/백준-알고리즘-1463-1로-만들기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol