2655번: 가장높은탑쌓기 LIS (DP) - Fastcampus
www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net # dp[i] = i번째 벽돌을 가장 밑바닥 벽돌로 하는 탑의 최대높이 # (j번째 벽돌 = i번째 벽돌 위에 올릴수 있는 앞 수열의 더 작고 가벼운 벽돌) # # 인덱스,면적,높이,무게 # bricks = [(5,1,5,2),(3,9,2,3),(1,25,3,4),(4,16,2,5),(2,4,4,6)] # # dp[1] = {(5,1,5,2)} = 5 # dp[2] = {(5,1,5,2),(3,9,2,3)}..
11053번: LIS 가장 긴 증가하는 부분수열 (DP) - Fastcampus
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net # dp[i] = i번째 수를 마지막 원소로 가지는 부분수열의 최대길이 # (j번째 수 = i번째 수와 연결되는 앞 수열의 작은 수) # # dp[i] = max(dp[j]) + 1, j < i # # nums = [10, 20, 10, 30, 20, 50] # # dp[0] = {10} = 1 # dp[1] = {10,20} = 2..