15. 합의 0 (11점)
N개의 정수를 가진 수열 A[1], A[2], . . . , A[N]이 주어진다.
수열을 여러 개의 부분으로 분할하려 한다. 제일 앞의 부분과 제일 뒤의 부분을 제외하고, 각각의 부분에있는 수들의 합은 0이여야 한다. 물론, 가장 앞 부분 또는 가장 뒷 부분의 수들의 합이 0인 경우도 가능하다.
합이 0인 부분의 개수 (부분에 속한 인덱스의 개수가 아니라, 나누어진 부분의 개수를 뜻함에 유의하라)가 가장 많도록 수열을 분할하라.
아래 그림에서 + 버튼을 누르면 수열의 해당 부분을 나눌 수 있고, - 버튼을 누르면 수열의 해당 부분을합칠 수 있다. 수열의 각 부분이,
• 수들의 합이 0이면 하얀색
• 수들의 합이 0이 아니지만, 가장 앞 부분이거나 가장 뒷 부분이면 파란색
• 수들의 합이 0이 아니고, 가장 앞 부분 또는 가장 뒷 부분이 아니면 빨간색의 배경으로 표시된다.
빨간색 배경의 부분이 없을 경우, 제출할 수 있다.
이 때, 하얀색 배경의 부분의 개수(부분에 속한 칸의 개수가 아님에 유의하라)가 가능한 가장 많다면, 점수의 100%를 받을 수 있다. 그렇지 않다면, 점수의 0%를 받는다.
========== 풀이 ==========
숫자가 몇개 되지 않으므로 누적합을 구하면 쉽게 해결 가능 하다.
위 표를 보면 앞에서 부터 0이되는 구간을 찾는 방법 부터 해서 .. 앞 부분을 하나씩 제외 하면서 누적 합을 구하면 쉽게 0이 되는 구간이 개수를 알 수 있다.
여기서는 4번에서 0이되는 구간이 /-4, 1, 6, 3 / -4, 4/ -3, 1, 5, -3 / 이렇게 3개가 나온다.