문제 개요
0과 1로만 구성된 임의의 크기의 이진 배열(binary array)과 정수 변수 base가 주어집니다. 이때 우리의 목표는 배열 전체가 '강력(powerful)'한 상태가 되도록 다른 요소들에게 힘을 빌려줄 수 있는 최소한의 1 개수를 계산하는 것입니다. 여기서 하나의 요소는 자신과 인접한 요소는 물론, base로 주어진 거리 이내에 있는 모든 요소에게 힘을 빌려줄 수 있습니다.
다양한 입력·출력 시나리오를 통해 문제를 살펴보겠습니다.
예제 1
입력 − int arr[] = {1, 1, 0, 1, 1, 0, 1}, int base = 7
출력 − 배열 전체를 강력하게 만들기 위해 필요한 최소 1의 개수: 1
설명 − 크기가 7인 이진 배열과 base 값 7이 주어졌습니다. 이는 첫 번째로 등장한 1이 배열 전체에 힘을 빌려줄 수 있음을 의미합니다. 따라서 arr[0]에 있는 단 하나의 1만으로 배열의 모든 요소를 커버할 수 있습니다.
예제 2
입력 − int arr[] = {1, 1, 0, 1, 1, 0, 1}, int base = 3
출력 − 배열 전체를 강력하게 만들기 위해 필요한 최소 1의 개수: 2
설명 − base 값이 3이므로 각 1은 자신을 포함해 거리 3 이내의 요소들에게만 힘을 빌려줄 수 있습니다. 따라서 앞쪽의 1이 초반 세 요소를 커버하고, 뒤쪽의 1이 나머지 구간을 커버하여 총 2개의 1만으로 배열 전체를 강력하게 만들 수 있습니다.
예제 3
입력 − int arr[] = {1, 1, 0, 1, 1, 0, 1}, int base = 1
출력 − Impossible to make entire array powerful (전체 배열을 강력하게 만드는 것은 불가능)
설명 − base 값이 1이면 각 1은 자기 자신에게만 힘을 가질 수 있습니다. 따라서 값이 0인 요소를 절대 커버할 수 없으므로, 배열 전체를 강력하게 만드는 것은 불가능합니다.
프로그램에서 사용된 접근 방식
임의의 크기를 가진 이진 배열과 정수 변수 base를 입력받습니다.
배열의 크기를 계산하고, 결과를 저장할 정수형 변수 val을 선언합니다.
val에 '강력한 배열을 만들기 위해 필요한 최소 1의 개수'를 반환하는 함수의 호출 결과를 저장합니다. 만약 불가능한 경우라면 -1을 반환하며, 이후 오류 메시지를 출력합니다.
Lend_Power(int arr[], int size, int base)함수 내부 동작은 다음과 같습니다.이진 배열과 같은 크기의 정수형 배열을 선언합니다.
임시 변수 temp는 -1로, count는 0으로 초기화합니다.
i를 0부터 배열 크기까지 반복하는 FOR 루프를 실행합니다. 루프 안에서 arr[i]가 1이면 temp를 i로 갱신하고, arr_2[i]에 temp 값을 저장합니다. 즉, arr_2[i]에는 인덱스 i까지 등장한 '가장 오른쪽에 있는 1의 위치'가 기록됩니다.
두 번째 FOR 루프를 실행합니다. reset_base를 i + base - 1로, reset_size를 size - 1로 설정한 뒤, set 변수에 arr_2[min(reset_base, reset_size)] 값을 대입합니다.
set이 -1이거나 set + base <= i이면 더 이상 진행이 불가능하므로 -1을 반환합니다.
i를 set + base로 갱신하고 count를 1 증가시킵니다.
모든 요소를 성공적으로 커버하면 count를 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int Lend_Power(int arr[], int size, int base)
{
int arr_2[size];
int temp = -1;
int count = 0;
for(int i = 0; i < size; i++)
{
if(arr[i] == 1)
{
temp = i;
}
arr_2[i] = temp;
}
for(int i = 0; i < size;)
{
int reset_base = i + base - 1;
int reset_size = size - 1;
int set = arr_2[min(reset_base, reset_size)];
if(set == -1 || set + base <= i)
{
return -1;
}
i = set + base;
count++;
}
return count;
}
int main()
{
int arr[] = {1, 1, 0, 1, 1, 0, 1};
int base = 2;
int size = sizeof(arr) / sizeof(arr[0]);
int val = Lend_Power(arr, size, base);
if(val == -1)
{
cout<<"Impossible to make entire array powerful";
}
else
{
cout<<"Minimum 1s to lend power to make whole array powerful are: "<<val;
}
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Minimum 1s to lend power to make whole array powerful are: 3
동작 원리 요약
이 알고리즘은 그리디(greedy) 방식으로 동작합니다. 현재 위치 i에서 커버 가능한 범위 [i, i + base - 1] 안에서 가장 오른쪽에 있는 1을 선택하면, 한 번의 선택으로 최대한 넓은 구간을 커버할 수 있습니다. arr_2 배열을 사전에 계산해 두면 각 범위에서 가장 오른쪽 1의 위치를 O(1) 시간에 찾을 수 있으므로, 전체 시간 복잡도는 O(n)으로 매우 효율적입니다. 위 예제에서는 base가 2이므로 세 개의 1이 필요하며, 만약 어떤 구간도 커버할 수 없다면 -1을 반환해 '불가능' 상태를 알립니다.