문제
코드
dp=[0]*100
def onetwo(n):
if n==1:
return 1
if n==2:
return 2
if n==3:
return 4
if dp[n]!=0:
return dp[n]
else:
dp[n]=onetwo(n-1)+onetwo(n-2)+onetwo(n-3)
return dp[n]
count=int(input())
a=[]
t=count
while count>0:
count=count-1
n=int(input())
a.append(onetwo(n))
for i in range(0,t):
print(a[i])
dp라는 배열을 만들었다. 숫자는 1,2,3의 합으로 만들어져야 하기 때문에 dp[n-1]+dp[n-2]+dp[n-3]으로 결과를 구했다. dp[n-1]이 나타내는 것은 입력받은 숫자에서 1을 한번 썻다고 가정하는것이다. 예를 들면 7을 입력받은 경우 dp[7-1]은 dp[6]은 1,2,3으로 6을 만드는 경우의 수 이다.
dp[1]은 1로 정하였다. dp[2]는 1+1, 2 이므로 2로 정하였다. dp[3]은 1+1+1, 1+2, 2+1, 3 이므로 4로 정하였다.
문제
코드
n=int(input())
dp=[0]*(n+1)
for i in range(0,n+1):
if i<=1:
dp[i]=0
continue
else:
dp[i]=dp[i-1]+1
if i%2==0:
dp[i]=min(dp[i//2]+1,dp[i])
if i%3==0:
dp[i]=min(dp[i//3]+1,dp[i])
print(dp[n])
dp라는 배열을 만들었다. dp[3]이면 1을 빼거나 3으로 나누거나 2로 나누었을 때 최소의 단계의 수를 나타낸다.dp에 0부터 입력받은 숫자까지 차례대로 채워넣는 방식으로 했다. dp[0]과 dp[1]은 0이므로 0을 넣었다. 그 후 1을 뺀 경우에는 이전단계에서 1을 더한것과 같다. 이것을 첫번째로 해준 이유는 밑에에서 min으로 비교하는 것 이전에 넣어줘야 dp에 최솟값이 들어가기 때문이다.
문제
코드