C++로 각 방사 스테이션의 최종 방사량 구하기

직선 위에 N개의 방사 스테이션이 나란히 놓여 있다고 가정해 보겠습니다. 각 스테이션은 음수가 아닌(non-negative) 방사 능력을 가지며, 인접한 스테이션들의 방사 세기를 일정한 규칙에 따라 증가시킵니다.

방사 세기가 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에 두 번째 스테이션의 기여분 1(=2-1)과 세 번째 스테이션의 기여분 1(=3-2)을 더해 3이 되고, 나머지 스테이션들도 같은 방식으로 계산하여 최종적으로 [3, 4, 4]를 얻게 됩니다.

접근 방법

핵심 아이디어는 매우 단순합니다. 모든 스테이션 i를 차례로 순회하면서, 위에서 설명한 규칙대로 좌우 이웃 스테이션들의 방사량에 기여분을 누적하는 것입니다. 이때 유효 방사량이 음수가 되는 순간 내부 반복을 중단하면 불필요한 연산을 줄일 수 있습니다.

C++ 구현

#include <iostream>
using namespace std;

void findFinalRadiation(int arr[], int n) {
    int result[n];
    for (int i = 0; i < n; i++)
        result[i] = 0;

    for (int i = 0; i < n; i++) {
        // 왼쪽 방향 이웃에게 기여분 누적
        for (int j = i - 1; j >= 0; j--) {
            int effect = arr[i] - (i - j);
            if (effect <= 0)
                break;
            result[j] += effect;
        }
        // 오른쪽 방향 이웃에게 기여분 누적
        for (int j = i + 1; j < n; j++) {
            int effect = arr[i] - (j - i);
            if (effect <= 0)
                break;
            result[j] += effect;
        }
        // 자기 자신의 원래 방사량 추가
        result[i] += arr[i];
    }

    cout << "각 스테이션의 최종 방사량 : ";
    for (int i = 0; i < n; i++)
        cout << result[i] << " ";
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    findFinalRadiation(arr, n);
    return 0;
}

실행 결과

각 스테이션의 최종 방사량 : 3 4 4

복잡도 분석

• 시간 복잡도: O(n²) — 각 스테이션이 좌우 이웃을 순회하며 기여분을 더합니다.
• 공간 복잡도: O(n) — 각 스테이션의 최종 방사량을 저장할 배열이 필요합니다.