#230
합이 0
N개의 정수를 가진 수열 A[1], A[2], …, A[N]이 주어진다.
수열을 여러 개의 부분으로 분할하려 한다. 제일 앞의 부분과 제일 뒤의 부분을 제외하고, 각각의 부분에 있는 수들의 합은 0이여야 한다. 물론, 가장 앞 부분 또는 가장 뒷 부분의 수들의 합이 0인 경우도 가능하다.
합이 0인 부분의 개수 (부분에 속한 인덱스의 개수가 아니라, 나누어진 부분의 개수를 뜻함에 유의하라) 가 가장 많도록 수열을 분할하라.
아래 그림에서 + 버튼을 누르면 수열의 해당 부분을 나눌 수 있고, - 버튼을 누르면 수열의 해당 부분을 합칠 수 있다. 수열의 각 부분이,
수들의 합이 0이면 하얀색
수들의 합이 0이 아니지만, 가장 앞 부분이거나 가장 뒷 부분이면 파란색
수들의 합이 0이 아니고, 가장 앞 부분 또는 가장 뒷 부분이 아니면 빨간색
의 배경으로 표시된다.
빨간색 배경의 부분이 없을 경우, 제출할 수 있다.
이 때, 하얀색 배경의 부분의 개수(부분에 속한 칸의 개수가 아님에 유의하라)가 가능한 가장 많다면, 점수의 100%를 받을 수 있다. 그렇지 않다면, 점수의 0%를 받는다.
문제 해결이 끝난 후 반드시 ‘제출’ 버튼을 눌러 제출해 주세요.
문제를 해결하려면 로그인해 주세요.
문제 형식
출처
- KOI 2023 1차대회 고등부 1교시 15번
- KOI 2023 1차대회 중등부 1교시 15번
- KOI 2023 1차대회 초등부 1교시 18번