본문 바로가기

부분합1

#1126 같은 탑(dynamic programming) 이 문제는 수열이 주어졌을 때, 각각의 수를 왼쪽, 오른쪽, 또는 사용치 않음으로 분류했을 때, 왼쪽 수열의 합과 오른쪽 수열의 합이 같은 경우, 그 값의 최대값이 얼마인가를 묻는 것입니다. 예를 들어서, 14 3 20 15 15 14 24 23 15 이란 값이 있다고 하죠. 그러면, 왼쪽에 [14] 오른쪽에 [14]란 수열이 있다면, 그 합이 14로 같기 때문에 같은 합이 될 수 있습니다. 하지만 이것은 최대값은 아닙니다. [14, 15]와 [14, 15]와 같이 쉽게 찾을 수 있는 값만 해도 29로 더 큰 값이 되기 때문이죠. [14, 20, 15, 15] 와 [3, 14, 24, 23] 로 나누면 64라는 최대값을 얻습니다. 여기서 중요한 것은 주어진 수열의 한 숫자는 왼쪽, 오른쪽, 또는 사용치않.. 2020. 1. 4.
728x90

티스토리툴바