이 문제에서 우리는 사용자가 제공하는 특정 한계 내에서 머무르는 방식으로 양의 방향 또는 음의 방향을 이동하는 유효한 방법을 찾아야 합니다.
여기에서 우리는 이동할 수 있는 최대값과 이동할 n개의 양수 값의 배열인 특정 최대 한계 K가 제공됩니다. K 값을 절대 교차하지 않도록 이동하려면 시퀀스, 즉 양수 또는 음수 방향을 반환해야 합니다.
주제를 더 잘 이해하기 위해 예를 들어 보겠습니다.
Input : K = 56 and the array is [25 , 14 , 31 , 16 , 5]. Output : positive positive negative positive positive.
설명
먼저 0 + a[0] =0+25 =25 <56 yes인지 확인한 다음 양의 방향으로 이동합니다.
이제 25 + a[1] =25+14 =39 <56 yes인지 확인하고 양의 방향으로 이동합니다.
이제 29 + a[2] =39+31 =70 <56인지 확인하고 39 - a[2] =39 - 31 =8> 0인지 확인한 다음 음의 방향으로 이동합니다. .
8 + a[3] =8+16 =24 <56 yes인지 확인하고 양의 방향으로 이동합니다.
16 + a[4] =16 + 5 =21 <56 yes인지 확인하면 양의 방향으로 이동합니다.
자, 이제 이 문제를 풀 수 있는 논리를 만들어 봅시다. 양의 방향으로 움직이는 것이 한계에 도달할지 여부를 확인해야 합니다. 그렇지 않다면 긍정적인 방향으로 움직이십시오. 그렇지 않으면, 음의 방향으로 이동하는 것이 하한인 0에 도달하는지 확인하십시오. 그렇지 않으면 음의 방향으로 이동하십시오. 둘 다 예이면 반품이 불가능합니다.
이 논리를 기반으로 코드를 생성하기 위해 따라야 하는 알고리즘은 -
알고리즘
Initially set position to 0. Step 1 : for i -> 0 to n , n is the length of array. Follow step 2 - 4. Step 2 : if initial_postition + a[i] < K, initial_position + = a[i]. Print “POSITIVE”. Step 3 : else if initial_postition - a[i] > 0, initial_position - = a[i]. Print “NEGATIVE”. Step 4 : else , print “NO MORE VALID MOVES”.
예시
이제 문제를 해결하기 위한 알고리즘의 구현을 보여주는 프로그램을 만들어 보겠습니다.
#include <iostream>
using namespace std;
void StepsTaken(int a[], int n, int k){
string res = "";
int position = 0;
int steps = 1;
for (int i = 0; i < n; i++) {
if (position + a[i] <= k && position + a[i] >= (-k)) {
position += a[i];
cout<<"POSITIVE \t";
}
else if (position - a[i] >= -k && position - a[i] <= k) {
position -= a[i];
cout<<"NEGATIVE \t";
} else {
cout << -1;
return;
}
}
cout << res;
}
int main(){
int a[] = { 12 , 24 , 9 , 17 , 8};
int n = sizeof(a) / sizeof(a[0]);
int k = 40;
StepsTaken(a, n, k);
return 0;
} 출력
POSITIVE POSITIVE NEGATIVE NEGATIVE POSITIVE