문제 개요
이 문제에서는 사용자가 지정한 특정 한계 내에 머물 수 있도록 양의 방향(positive) 또는 음의 방향(negative)으로 이동하는 유효한 경로를 찾아야 합니다.
구체적으로, 최대 이동 한계값 K와 n개의 양수로 이루어진 배열이 주어집니다. 우리가 해야 할 일은 각 단계에서 이동 값을 더하거나 빼면서 위치가 절대 K 범위를 벗어나지 않도록 하는 이동 방향(양수/음수)의 순서를 구하는 것입니다.
입력 및 출력 예시
Input : K = 56, 배열 = [25 , 14 , 31 , 16 , 5]
Output : positive positive negative positive positive
동작 원리
예시를 단계별로 살펴보겠습니다.
먼저 0 + a[0] = 0 + 25 = 25 < 56 이므로 조건을 만족합니다. 따라서 양의 방향으로 이동합니다.
다음으로 25 + a[1] = 25 + 14 = 39 < 56 이므로 역시 양의 방향으로 이동합니다.
이번에는 39 + a[2] = 39 + 31 = 70 > 56 이므로 양의 방향은 불가능합니다. 대신 39 - a[2] = 39 - 31 = 8 > 0 을 확인하면 음의 방향으로 이동해도 하한선을 넘지 않습니다. 따라서 음의 방향으로 이동합니다.
그다음 8 + a[3] = 8 + 16 = 24 < 56 이므로 양의 방향으로 이동합니다.
마지막으로 24 + a[4] = 24 + 5 = 29 < 56 이므로 양의 방향으로 이동합니다.
풀이 로직
이제 문제를 해결하기 위한 핵심 로직을 정리해 보겠습니다.
- 현재 위치에서 해당 값을 더했을 때 상한 K를 초과하는지 확인합니다. 초과하지 않으면 양의 방향으로 이동합니다.
- 초과한다면, 현재 위치에서 값을 뺐을 때 하한(-K 또는 0) 미만이 되는지 확인합니다. 문제가 없다면 음의 방향으로 이동합니다.
- 두 방향 모두 불가능하다면 더 이상 유효한 이동이 없으므로 '불가능'을 반환합니다.
알고리즘
위 로직을 바탕으로 코드 작성 시 따라야 할 알고리즘은 다음과 같습니다.
초기 위치를 0으로 설정한다.
Step 1 : i -> 0부터 n까지 반복한다. (n은 배열의 길이) Step 2~4를 수행한다.
Step 2 : 초기_위치 + a[i] <= K 라면, 초기_위치 += a[i]. "POSITIVE"을 출력한다.
Step 3 : 아니고, 초기_위치 - a[i] >= -K 라면, 초기_위치 -= a[i]. "NEGATIVE"를 출력한다.
Step 4 : 둘 다 아니라면, "NO MORE VALID MOVES"를 출력한다.
C++ 구현 예제
이제 위 알고리즘을 실제 코드로 구현한 프로그램을 살펴보겠습니다.
#include <iostream>
using namespace std;
void StepsTaken(int a[], int n, int k){
string res = "";
int position = 0;
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
마무리
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 각 단계에서 양의 방향과 음의 방향을 순차적으로 검사하여 범위 내에 머무는 경로를 찾아내며, 어떤 방향으로도 이동할 수 없는 경우 -1을 출력해 이동이 불가능함을 알립니다. 이러한 접근 방식은 제약 조건이 있는 경로 탐색 문제에서 자주 활용되는 그리디(greedy) 기법의 좋은 예시입니다.