dp

DP-가장 높은 탑 쌓기

가장 높은 탑 쌓기 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다. (조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. ▣ 입력설명 입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터..

DP 최대선 연결하기

▣ 출력설명 첫 줄에 겹치지 않고 그을 수 있는 최대선의 개수를 출력합니다. ▣ 입력예제 1 10 4 1 2 3 9 7 5 6 10 8 ▣ 출력예제 1 6 n=int(input()) arr=list(map(int,input().split())) dp=[0]*(n+1) dp[1]=1 res=0 for i in range(2,n): max=0 for j in range(i-1,0,-1): if arr[j]

DP - Top-Down 방식과 Bottom-up

# bottom-top 방식 ''' n=int(input()) dp=[0]*(n+1) dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n]) ''' # TopDown 방식 Dfs사용 def dfs(n): if dp[n]>0: return dp[n] if n==1 or n==2: return n else: dp[n]=dfs(n-1)+dfs(n-2) return dp[n] n=int(input()) dp=[0]*(n+1) print(dfs(n)) 말 그대로 Top-Down방식은 위에서부터 아래로 이동해가면서 최적의 해를 찾아가는방식이고 Bottom-up은 반대이다 다만, Top-Down은 보통 DFS를 많이사용하는것같다.주의하자