문제 개요
일직선 위에 N개의 스테이션이 놓여 있고, 각 스테이션은 음수가 아닌 고유의 방사 능력(radiation power)을 가지고 있다고 가정해 보겠습니다. 흥미로운 점은 각 스테이션이 자신의 방사 능력을 이용해 양옆의 인접 스테이션들을 증폭시킬 수 있다는 것입니다.
구체적인 규칙은 다음과 같습니다. 방사 능력이 R인 스테이션 i는 왼쪽에 있는 (i-1)번째 스테이션의 방사 능력을 R-1만큼, (i-2)번째 스테이션의 방사 능력을 R-2만큼 높입니다. 오른쪽 방향도 마찬가지로 (i+1)번째 스테이션을 R-1만큼, (i+2)번째 스테이션을 R-2만큼 높입니다. 이처럼 거리가 멀어질수록 기여 값이 1씩 줄어들며, 기여 값이 0 이하로 떨어지면 더 이상 영향을 주지 않습니다.
예시로 이해하기
배열이 Arr = [1, 2, 3]일 때를 살펴보겠습니다. 각 위치의 새로운 방사 값은 다음과 같이 계산됩니다.
[1 + (2 − 1) + (3 − 2), 2 + (1 − 1) + (3 − 1), 3 + (2 − 1)] = [3, 4, 4]
즉, 첫 번째 스테이션은 자기 자신의 값 1에 오른쪽 이웃들의 기여를 받아 3이 되고, 두 번째와 세 번째 스테이션도 양옆 스테이션들의 기여를 합산해 각각 4가 됩니다.
해결 아이디어
핵심 아이디어는 매우 단순합니다. 각 스테이션 i를 기준으로, 위에서 설명한 규칙대로 유효 방사 값(effective radiation)이 0 이하가 될 때까지 인접 스테이션들의 방사 능력을 하나씩 더해 나가는 시뮬레이션을 수행하면 됩니다.
- 크기가 N인 결과 배열을 0으로 초기화합니다.
- 각 스테이션 i에 대해 자기 자신의 방사 값을 결과 배열에 더합니다.
- 왼쪽 방향으로는 R-1, R-2, … 순서로 값을 감소시키며 이웃 스테이션에 더하고, 값이 0이 되면 중단합니다.
- 오른쪽 방향에 대해서도 동일한 과정을 반복합니다.
- 모든 스테이션에 대한 처리가 끝나면 결과 배열이 곧 각 스테이션의 최종 방사 값입니다.
C++ 구현 코드
#include <iostream>
#include <vector>
using namespace std;
// 각 스테이션의 최종 방사 값을 계산하는 함수
vector<int> findFinalRadiation(const vector<int>& stations) {
int n = stations.size();
vector<int> result(n, 0);
for (int i = 0; i < n; i++) {
// 자기 자신의 방사 값
result[i] += stations[i];
// 왼쪽 방향으로 R-1, R-2, ... 만큼 전달
int effect = stations[i] - 1;
for (int j = i - 1; j >= 0 && effect > 0; j--, effect--)
result[j] += effect;
// 오른쪽 방향으로 동일하게 전달
effect = stations[i] - 1;
for (int j = i + 1; j < n && effect > 0; j++, effect--)
result[j] += effect;
}
return result;
}
int main() {
vector<int> stations = {1, 2, 3};
vector<int> answer = findFinalRadiation(stations);
cout << "최종 방사 값 : ";
for (int val : answer)
cout << val << " ";
return 0;
}
실행 결과
최종 방사 값 : 3 4 4
복잡도 분석
시간 복잡도: O(N × M). 여기서 M은 배열 내 최대 방사 값입니다. 한 스테이션이 최대 R-1개의 이웃에 영향을 줄 수 있기 때문입니다.
공간 복잡도: O(N). 결과를 저장하기 위해 크기 N의 배열 하나가 필요합니다.
마무리 팁
방사 값이 매우 큰 경우에는 누적합(prefix sum) 기법을 활용해 구간별 기여도를 한 번에 처리하면 성능을 더욱 개선할 수 있습니다. 다만 일반적인 코딩 테스트 수준의 입력에서는 위의 직관적인 시뮬레이션 방식만으로 충분히 문제를 해결할 수 있습니다.