스칼렛의 코딩라이프

이게 어떻게 피보나치 수 2 문제이지..? 피보나치 수 문제가 더 어렵고 이게 오리지널 같은데.. 단계별로 풀기에서 동적계획법 단계에 들어가면 바로 어려운 것 부터 나오는건가..? 신기하네.. a=int(input()) dp=[0]*1001 dp[1]=1 for i in range(2,a+1): dp[i]=(dp[i-2]+dp[i-1]) print(dp[a])

a=int(input()) dp=[0]*1001 dp[1]=1 dp[2]=2 for i in range(3,a+1): dp[i]=(dp[i-2]+dp[i-1])%10007 print(dp[a])

아무리 생각해도 동적계획법에 좀 익숙 해 져야 할 필요가 있을 것 같다. 그래서 알고리즘 분류로 동적계획법 문제를 풀기로 했다. 일단 좀 쉬워보이는 것부터 했음 dp=[0]*12 dp[1]=1 dp[2]=2 dp[3]=4 for i in range(4,12): dp[i]=dp[i-3]+dp[i-2]+dp[i-1] N=int(input()) for i in range(N): a=int(input()) print(dp[a]) 동적계획법은 점화식을 찾아 내는게 90% 인 것 같다. 마치 수능 수리영역의 마지막 문제같은 느낌.. 나같은 사람은 카드를 직접 다 그려서 맞추는.. 그런.. 아무튼 다 풀고 나면 많이 익숙 해 졌으면 좋겠다.

하루 종일 고민했는데... 결국 풀이를 참고했다. import sys input=sys.stdin.readline A=input().upper() B=input().upper() a=len(A) b=len(B) dp=[[0]*(b) for _ in range(a)] for i in range(1,a): for j in range(1,b): if A[i-1]==B[j-1]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) print(dp[-1][-1]) 지금까지는 1차원적으로 DP수열에 저장하는것으로 했었는데 이건 또 2차원수열.. 어떤지 어떻게 해도 답이 안나오더라.. 하기 블로그 참고해서 이해했다 LCS 풀이 [백준알고리즘] 9251..

이게 어떻게,, 어떻게,, 어떻게 LIS 응용인지 모르겠지만,, 처음에는 제일 겹쳐있는게 많은 선 부터 끊고, 그 선이 없는 새로운 리스트를 반환해서 그 다음 겹치는게 많은 선을 끊고, 그리고 겹치는게 없어질 때까지 하는것으로 코드를 짰었는데, 겹치는 수가 같은데 경우에 수가 다를 수도 있다는 생각을 하니 막막.. 다른 분 풀이를 봤는데 솔직히 잘 이해가 안된다.. 그냥 받아들여야지... 이해가 될랑 말랑.. N=int(input()) nl=[list(map(int,input().split())) for _ in range(N)] nl=sorted(nl,key=lambda x:x[0]) dp=[1]*N for i in range(N): for j in range(i): if nl[i][1]>nl[j][1..

가장 긴 증가하는 부분수열 문제를 풀고 이건 반대로 감소하는 부분 수열의 최대 값을 더해서 합 한 다음에 1을 빼면 되지 않을까 생각해서 풀었는데, 계속 틀렸다고 나와서 아예 다른 방법으로 풀다가 맞긴 맞았다. import sys input=sys.stdin.readline N=int(input()) ary=list(map(int,input().split())) dp=[1]*N dp2=[1]*N for i in range(N): for j in range(i): if ary[i]>ary[j]: dp[i]=max(dp[i],dp[j]+1) for i in range(N-1,-1,-1): for j in range(N-1,i,-1): if ary[i]>ary[j]: dp2[i]=max(dp2[i],dp2[j..