BOJ 8203 Lollipop
BOJ 8203 Lollipop
문제 내용
1과 2만으로 이루어진 길이 의 배열이 있습니다. 다음의 쿼리를 개 처리하세요.
- : 합이 인 구간이 존재한다면, 그러한 구간을 아무거나 하나 찾아서 그 시작 위치와 끝 위치를 순서대로 출력합니다. 그렇지 않다면
NIE를 대신 출력합니다.
입력
첫 줄에 과 이 주어집니다. ()
다음 줄에 배열의 정보가 주어집니다. T는 2, W는 1입니다.
다음 줄에 걸쳐서 쿼리의 값 가 한 줄에 하나씩 주어집니다. ()
출력
각 쿼리에 대해 정답을 한 줄에 출력합니다.
문제 풀이
스포일러
배열 전체가 2로만 이루어져 있다면, 짝수만 만들 수 있음이 자명하고, 각각의 짝수는 쉽게 만들 수 있습니다.
그렇지 않다면 2로만 이루어진 가장 긴 prefix와 가장 긴 suffix를 찾을 수 있습니다. 배열 전체의 총합이 이고 prefix와 suffix 중 짧은 것의 길이가 일 때, 이상 이하의 수 중에서는 와 홀짝이 같은 수들만 만들 수 있습니다.
이제 일반성을 잃지 않고 짧은 쪽이 prefix라고 하면, 그 prefix를 제외한 구간의 시작점에는 1이 존재합니다. 이를 이용하여 다음의 과정을 거쳐 1 이상 이하의 모든 합을 만들 수 있습니다.
- 오른쪽으로 확장하면서 원소를 하나씩 추가합니다.
- 방금 추가된 원소가 1이면, 기존 구간합 + 1의 값을 만들 수 있습니다.
- 방금 추가된 원소가 2이면, 맨 앞의 1을 빼서 기존 구간합 + 1을 만들 수 있고, 맨 앞의 1을 다시 더해서 기존 구간합 + 2를 만들 수 있습니다.
이제 가능한 모든 의 값에 대해 답을 미리 구해둔 뒤에 각 쿼리가 요구하는 에 대한 답을 꺼내서 출력하면 됩니다.
Last updated on