문제 설명
초기값을 가진 이진 배열 arr[]와 두 변수 a, b가 주어집니다. 배열의 각 요소를 통과하는 방법은 다음 두 가지입니다.
arr[i] == 1인 경우: a에서 1단위를 사용하면 b에는 변화가 없습니다. 반대로 b에서 1단위를 사용하면 a가 1만큼 증가합니다. (단, a의 값은 원래 값보다 커질 수 없습니다.)
arr[i] == 0인 경우: a 또는 b 어느 쪽에서든 1단위를 사용할 수 있습니다.
목표는 주어진 조건 안에서 배열의 최대한 많은 요소를 통과하는 것입니다. 예시를 통해 자세히 살펴보겠습니다.
입력 예제 1
arr[] = {0, 0, 0, 1, 1}, a = 2, b = 2
출력
5
설명
1번째 요소: a에서 1단위 사용 (a = 1, b = 2)
2번째 요소: a에서 1단위 사용 (a = 0, b = 2)
3번째 요소: b에서 1단위 사용 (a = 0, b = 1)
4번째 요소: b에서 1단위 사용 → a가 1 증가 (a = 1, b = 0)
5번째 요소: a에서 1단위 사용 (a = 0, b = 0)
모든 요소를 통과했으므로 정답은 5입니다.
입력 예제 2
arr[] = {1, 1, 1, 0, 1}, a = 1, b = 2
출력
4
접근 방법
그리디(greedy) 방식으로 배열을 앞에서부터 순회하면서 상황에 맞게 a와 b를 사용합니다.
- MaxElements() 함수에서 a의 원래 값을 저장할 변수 Oa와 정답을 저장할 변수 max를 int형으로 선언하고 0으로 초기화합니다.
- i = 0부터 i < size까지 반복하며 배열의 모든 요소를 확인합니다.
- a와 b가 모두 0이면 더 이상 진행할 수 없으므로 반복문을 종료(break)합니다.
- a == 0인 경우: 현재 요소가 1이면 b에서 1을 차감한 뒤 a = min(Oa, a + 1)로 갱신하여 a가 원래 값을 초과하지 않도록 합니다. 현재 요소가 0이면 단순히 b에서 1을 차감합니다.
- b == 0인 경우: 단순히 a에서 1을 차감합니다.
- arr[i] == 1 && a < Oa인 경우: b에서 1을 차감하고 a = min(Oa, a + 1)로 갱신합니다. 이렇게 하면 b를 소모하여 a를 회복할 수 있습니다.
- 그 외의 경우: a에서 1을 차감합니다.
- 요소를 하나 통과할 때마다 max를 1씩 증가시키고, 반복문이 끝나면 max를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int MaxElements(int arr[], int a, int b, int size){
// Oa에는 a의 원래 값이 저장됨
int Oa = a;
int max = 0;
// 이진 배열을 순회
for (int i = 0; i < size; i++){
// a와 b가 모두 0이면 반복문 종료
if (a == 0 && b == 0)
break;
// a가 없으면 b 사용
else if (a == 0){
// arr[i] == 1이면 a를 1 증가
if (arr[i] == 1){
b -= 1;
// 원래 값을 초과하지 않는지 검사
a = min(Oa, a + 1);
}
else
b -= 1;
}
// b가 없으면 a 사용
else if (b == 0)
a--;
// arr[i] == 1이면 b 사용
else if (arr[i] == 1 && a < Oa){
b -= 1;
a = min(Oa, a + 1);
}
else
a--;
max++;
}
return max;
}
// main 함수
int main(){
int arr[] = { 1, 1, 1, 0, 1 };
int size = sizeof(arr) / sizeof(arr[0]);
int a = 1;
int b = 2;
cout << MaxElements(arr, a, b, size);
return 0;
}
출력
4
복잡도 분석
배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 공간은 상수 수준으로 O(1)입니다.