흙금이네 블로그

아이디어 동적 계획법으로 감소하는 수열 합의 최댓값을 구한다. 풀이 #1 (Python) 리스트 dp에 수열 A와 같은 값들을 저장한다. 이중 for문에서 수열의 두 요소를 비교하여 수가 감소할 때 더 큰 부분 수열의 합으로 갱신해 나간다. max(dp)로 전체 감소 부분 수열의 합 중 가장 큰 값을 찾아 출력한다. def solution(): N = int(input()) A = tuple(map(int, input().split())) dp = list(A) for i in range(N): for j in range(i+1, N): if A[j] dp[j]: dp[j] = dp[i]+A[j] print(max(dp)) solution() 풀이 #2 (Jav..