https://www.acmicpc.net/problem/25608
문제 요약
- 길이 M인 N개의 수열이 주어짐(M = 10000, N = 10)
- 수열을 통째로 순서를 바꿀수는 있으나, 수열 내부의 순서는 못바꿈
- 최대 연속합 구하기
접근법
- 10!로 배치하고 각각으로 연속합을 구하기에는 무리가 있어 보임
- 구해놓을 것이 일단
- 각각 수열의 최대 연속합은 일단 구함
- 전체 합
- 왼쪽 끝에서부터의 최대 연속합
- 오른쪽 끝에서부터의 최대 연속합
- 이제 붙여본다
- 왼쪽 ||||| 오른쪽
- |||||에 들어갈 것들은 다른 수열인데, 수열 전체의 합이 음수이면 안쓰면 그만이므로, 0으로 처리하면 쉬워짐
- 즉 |||||의 합 = 전체 수열의 합 - 왼쪽 - 오른쪽, 왜냐면 음수를 0으로 처리했으니까 이게 가능함
- 왼쪽 - 오른쪽 끝에서부터의 최대 연속합, 오른쪽 - 왼쪽 끝에서부터의 최대 연속합 즉,
- ... >>> ||||| <<< .... 이런 식으로 구성을 해 볼 수 있음
- 왼쪽, 오른쪽 가능한 경우의 수는 10 * 10 = 100
- 최종 답은 그래서, 다음 중에 큰 것
- 각각 수열에서 최대 연속합
- 붙였을때의 최대 연속합
newbieski