양의 정수 K와 정수들을 담고 있는 배열 Ops[]가 주어집니다. 이 문제의 목표는 K에 특정 연산을 반복 적용하여 K가 0보다 작아질 때까지 필요한 연산 횟수를 구하는 것입니다. 연산 규칙은 다음과 같습니다.
첫 번째 연산은 K + Ops[0]입니다. 즉, 배열의 첫 번째 요소를 K에 더합니다.
그다음부터는 K < 0이 될 때까지 Ops[i]를 계속해서 K에 더합니다. 이때 인덱스 i는 순환(circular) 방식으로 진행됩니다. 즉, 0 ≤ i < N(N은 배열 Ops[]의 크기) 범위에서 i가 마지막 요소 Ops[N-1]에 도달하면 다시 i = 0부터 시작합니다.
참고: K < 0이 될 때까지 Ops[i]를 계속 더하되, 인덱스가 배열의 끝에 도달하면 처음으로 되돌아가 순환적으로 반복합니다.
효율적인 해결을 위해 먼저 배열 Ops[]의 모든 요소의 합을 확인합니다. 만약 합이 0보다 크거나 같다면 아무리 반복해도 K는 절대 0 미만으로 줄어들지 않으므로 -1을 반환합니다. 그렇지 않다면 Ops[i]를 K에 계속 더하면서 K < 0인지 검사하고, 조건이 만족되면 반복문을 종료합니다.
연산이 수행될 때마다(K + Ops[i]) 연산 횟수 카운트를 1씩 증가시킵니다.
예제로 이해하기
예제 1
입력:
ops[] = { -4, 2, -3, 0, 2 }, K = 5출력: 필요한 연산 횟수 = 3
설명: K는 5에서 시작하며, 연산 과정은 다음과 같습니다.
1. K + ops[0] = 5 + (-4) = 1 2. K + ops[1] = 1 + 2 = 3 3. K + ops[2] = 3 + (-3) = 0
예제 2
입력:
ops[] = { 5, 5, 3, -2 }, K = 10출력: K를 줄일 수 없습니다!!
설명: K는 10에서 시작하며, 연산 과정은 다음과 같습니다.
1. K + ops[0] = 10 + 5 = 15 2. K + ops[1] = 15 + 5 = 20 3. K + ops[2] = 20 + 3 = 23 4. K + ops[3] = 23 + (-2) = 22 5. K + ops[0] = 22 + 5 = 27 6. K + ops[1] = 27 + 5 = 32 7. ………
미리 배열의 합을 계산해 보면 ops[] = 5 + 5 + 3 - 2 = 11이며, 여기에 K = 10을 더한 값은 항상 양수입니다. 따라서 K는 절대 0 미만으로 줄어들 수 없습니다.
알고리즘 접근 방식
임의의 정수들로 초기화된 정수 배열 ops[]를 준비합니다.
변수 K에 양의 값을 설정합니다.
함수 countOperations(int op[], int n, int k)는 배열 Ops[]와 그 길이를 매개변수로 받아, K를 0 미만으로 만드는 데 필요한 연산 횟수를 반환합니다.
연산 횟수를 저장할 변수 count를 0으로 초기화합니다.
배열 ops[] 요소들의 합을 계산하여 sum에 저장합니다. 만약 sum ≥ 0이라면 -1을 반환합니다.
그렇지 않다면 k > 0인 동안 ops[i]를 계속 더하고 count를 증가시킵니다. k < 0이 되면 반복문을 종료합니다.
최종 결과로 count를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
long countOperations(int op[], int n, int k){
long count = 0;
int sum=0;
int i=0;
for(int i=0;i<n;i++){
sum+=op[i];
}
if(sum-k>=0)
{ return -1; } // sum-k가 항상 양수 또는 0이므로 k는 절대 감소할 수 없음
while(k>0){
for(i=0;i<n;i++){
if(k>0){
count++;
k+=op[i];
}
else
{ break; }
}
}
return count;
}
int main(){
int Ops[] = { 1,-1,5,-11};
int len= sizeof(Ops) / sizeof(Ops[0]);
int K=10;
long ans=countOperations(Ops,len,K);
if(ans==-1)
{ cout<<"K cannot be reduced!!"; }
else
{ cout<<"Number of operations : "<<ans; }
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Number of operations : 8