Most Muscular Most Muscular

기출: 백준 #9251 stringA = ' ' + input() stringB = ' ' + input() m = len(stringA) n = len(stringB) LCS = [[0 for __ in range(n)] for _ in range(m)] for i in range(1, m): for j in range(1, n): if stringA[i] == stringB[j]: LCS[i][j] = LCS[i-1][j-1] + 1 else: LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) print(LCS[m-1][n-1])

기출: 백준 #11055 # d[n] = n번째 수를 선택한 경우의 최댓값 n = int(input()) arr = list(map(int,input().split())) d = [-1 for _ in range(n)] d[0] = arr[0] for i in range(1, n): maxVal = arr[i] for j in range(i): if arr[j]

기출 : BOJ #12865 현재 상황을 무게가 N이라고 가정했을 때 현재 무게일때 가치의 최댓값(D[n])은 (직전 최댓값(D[n-ai])에 직전에 선택한 물건의 가치(val[ai])를 더한 것)의 최댓값이다 이를 점화식으로 표현하면 다음과 같다 D[n] = max(D[n-ai]+val[ai]) from copy import deepcopy # D[n] = 무게가 n일때 가질 수 있는 가치의 최댓값, [최댓값을 만들 때 선택된 것들] # D[n] = max(D[n-ai]+val[ai]) ans = 0 n, k = map(int,input().split()) weight, val = list(), list() for i in range(n): w, v = map(int,input().split()) we..

기출 : BOJ #1932 n번째 줄 m번째 위치를 고르는 경우 이는 n-1번째 줄의 m-1번째, m번째 위치로부터 내려온다 (확장성) 이를 고려하면 점화식은 다음과 같다 D[n][m] = n번째 줄 m번째 숫자를 고르는 경우 최댓값 D[n][m] = max(D[n-1][m-1], D[n-1][m]) + tri[n][m] # d[n][m] = max(d[n-1][m-1], d[n-1][m]) + tri[n][m] n = int(input()) tri = list() d = [[0 for j in range(i+1)] for i in range(n)] for _ in range(n): tri.append(list(map(int,input().split()))) d[0][0] = tri[0][0] for i..

기출 : BOJ #1149 현재 상황을 여러 상황으로 쪼갤 수 있고 각 상황은 직전 선택에서 나온다 (확장성) n번째 색으로 0번 색을 고르는 경우의 최솟값을 D[n][0]이라고 하면 다음과 같은 점화식이 나온다 D[n][0] = min(D[n-1][1], D[n-1][2]) + rgbs[n] # d[n][0] : n번째 r 선택하는 경우 # d[n][0] = min(d[n-1][1], d[n-1][2]) + val[n] n = int(input()) rgbs= list() d = [[0 for _ in range(3)] for __ in range(n)] for _ in range(n): rgbs.append(list(map(int,input().split()))) d[0][0], d[0][1], d[..

기출 : BOJ #1912 현재 상황은 현재 숫자를 포함하는 경우, 포함하지 않는 경우로 나뉜다 현재 숫자를 포함하는 경우 최댓값(d[n][1])은 직전 숫자를 포함하는 경우(d[n-1][1] + arr[n])와 포함하지 않는 경우(arr[n])로 나눌 수 있고 현재 숫자를 포함하지 않는 경우 최댓값(d[n][0])은 직전 상황의 최댓값이다 (max(d[n-1]) 이를 구현하면 다음과 같다 # d[n][1] = n번째를 포함했을 경우의 최댓값 # d[n][0] = n 포함 x 최댓값 n = int(input()) arr = list(map(int, input().split())) d = [[0 for _ in range(2)] for i in range(n)] d[0][0] = arr[0] d[0][1]..

기출 : BOJ #1904 직전에 0이 나오는 경우와 1이 나오는 경우로 나눌 수 있다 D[n][m] = n번째 자리에 m이 나오는 경우의 가짓수 D[n][0] = D[n-2][0] + D[n-2][1] D[n][1] = D[n-1][0] + D[n-1][1] 이렇게 문제를 해결해도 되지만 주어진 메모리 조건에 벗어났다 문제에서 원하는 것은 D[n][0] + D[n][1] 이므로 점화식을 새로 정의했다 D[n] = D[n][0] + D[n][1] D[n] = D[n-1] + D[n-2] n = int(input()) # d[n][0] = d[n-2][0] + d[n-2][1] # d[n][1] = d[n-1][0] + d[n-1][1] # d[n] = d[n-1] + d[n-2] d = [0 for _ ..

기출 : BOJ #2579 선택한 계단들에 새로운 계단을 추가할 수 있다 (확장성) 현재 상황을 직전 상황들로 표현할 수 있다 (점화식 작성 가능) D[n][m] = n번째 계단을 선택할 때 연속으로 m개의 계단을 선택한 경우 최댓값 D[n][1] = max(D[n-2]) + score[n] D[n][2] = D[n-1][1] + score[n] 계산할 범위는 3~n까지 이다 # d[n][2] = d[n-1][1] + score[n] # d[n][1] = max(d[n-2]) + score[n] # d[1][1] = score[1] # d[2][1] = score[2] # d[1][2] = 0 # d[2][2] = score[1] + score[2] 걔 n = int(input()) d = [[0 for..