Lv.3 파괴되지 않은 건물 [C++]

문제 링크

성공 여부(걸린 시간): 성공 (1시간 12분 실패 -> 성공)

아이디어

이 문제는 스킬이 최대 25만 번, 보드는 최대 1000×1000이라서 스킬을 매번 보드에 직접 적용하면 시간초과가 난다.
핵심은 “직사각형 구간 업데이트를 빠르게 누적”한 뒤, 마지막에 한 번에 보드에 반영하는 것이다.

 

내가 처음 실패했던 방식은 “각 스킬마다 (start_x~end_x) 행을 직접 돌면서 가로 누적합 형태로 갱신”하는 아이디어였다. 누적합을 쓰는 것처럼 보이지만, 스킬 하나당 세로 길이만큼 반복이 발생한다.

• 스킬 1개 처리: 최악 O(N) (세로 길이 1000까지 가능)
• 스킬 K개: O(KN) → 25만×1000 = 2.5억 수준의 갱신이 발생 가능
• 여기에 누적합/검사까지 더해져 효율성에서 시간초과

즉, 실패 원인은 “구간 업데이트를 진짜 O(1)로 만들지 못했다”는 점이다.

사실 여기서 좀 억울한 부분도 있는데 내 기존 실패 로직으로 계산을 해보면

최악의 경우 2000 * 250000 = 500,000,000 으로 약 5초 정도이다.

그러나 제한시간 안내에

• 정확성 테스트 : 10초
• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

라고 되어있기에 괜찮겠거니 했는데 이럴거면 미리 말해주지... 싶지만 진작 최적화를 잘하면 좋을 듯 하다.

 

아무튼 이를 해결하려면 스킬 1개를 처리할 때 행을 도는 것이 아니라, 2차원 차분 배열(diff, imos)을 써서 직사각형을 네 꼭짓점만 갱신(O(1))해야 한다.

• 스킬 반영: 스킬당 O(1) → O(K)
• 누적합 복원: O(NM)
• 최종 검사: O(NM)
  총합 O(K + NM)로 통과한다.

이모스(2차원 차분 배열) 설명 + 예시

보드가 3×4라고 하자(행 3, 열 4). 변화량을 저장할 배열 diff를 0으로 시작한다.

초기 상태:

0 0 0 0
0 0 0 0
0 0 0 0

이제 (r1,c1)=(0,1)부터 (r2,c2)=(1,2)까지 직사각형에 +5를 더한다고 하자.
즉 아래 영역에만 +5가 들어가야 한다.

원하는 최종 변화량(정답 모습):

0 5 5 0
0 5 5 0
0 0 0 0

직접 모든 칸에 +5를 더하면 느리니까, diff에 네 점만 찍는다(2D imos 규칙).
배열 범위 안에서만 처리한다고 가정하면 다음 4개다.

• diff[r1][c1] += 5 → diff[0][1] += 5
• diff[r1][c2+1] -= 5 → diff[0][3] -= 5
• diff[r2+1][c1] -= 5 → diff[2][1] -= 5
• diff[r2+1][c2+1] += 5 → diff[2][3] += 5

이때 diff는 이렇게 “모서리 정보만” 들어간다:

0  5  0 -5
0  0  0  0
0 -5  0  5

이제 이 diff에 대해

1. 가로 누적합을 하면(각 행에서 왼→오):

0  5  5  0
0  0  0  0
0 -5 -5  0

2. 세로 누적합을 하면(각 열에서 위→아래):

0  5  5  0
0  5  5  0
0  0  0  0

원래 원하는 직사각형 영역만 +5가 채워진다.

여기서 (r2+1, c2+1)에 +5를 해주는 이유는 포함-배제 형태로 중복 차감을 복구하기 위해서다.
r2+1 줄과 c2+1 칸에서 각각 끊어주다 보면 오른쪽-아래 영역은 “두 번 빼진 상태”가 되는데, 그걸 +로 한 번 되돌려 정확히 0이 되게 만드는 점이 (r2+1, c2+1)이다.

이 문제의 스킬은 공격/회복이 섞여 있으므로 degree에 부호만 붙여 같은 방식으로 처리하면 된다.

• type 1(공격): -degree
• type 2(회복): +degree

풀이코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int N, M;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    N = board.size();
    M = board[0].size();

    // 변화량을 누적할 2차원 차분 배열(이모스)
    vector<vector<int>> skill_sum(N, vector<int>(M, 0));

    for (vector<int> cur_skill : skill) {
        // type 1: 공격(내구도 감소) -> 음수
        // type 2: 회복(내구도 증가) -> 양수
        int sign = (cur_skill[0] == 1) ? -1 : 1;
        int degree = cur_skill[5] * sign;

        int start_x = cur_skill[1];
        int start_y = cur_skill[2];
        int end_x   = cur_skill[3];
        int end_y   = cur_skill[4];

        // (start_x, start_y) ~ (end_x, end_y)에 degree를 더하는 2D imos 4점 갱신
        skill_sum[start_x][start_y] += degree;

        if (end_x + 1 < N) {
            skill_sum[end_x + 1][start_y] -= degree;
        }
        if (end_y + 1 < M) {
            skill_sum[start_x][end_y + 1] -= degree;
        }
        if (end_x + 1 < N && end_y + 1 < M) {
            skill_sum[end_x + 1][end_y + 1] += degree;
        }
    }

    // 가로 누적합
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M - 1; j++) {
            skill_sum[i][j + 1] += skill_sum[i][j];
        }
    }

    // 세로 누적합
    for (int j = 0; j < M; j++) {
        for (int i = 0; i < N - 1; i++) {
            skill_sum[i + 1][j] += skill_sum[i][j];
        }
    }

    // 최종 내구도 계산 및 생존 카운트
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] + skill_sum[i][j] <= 0) {
                answer++;
            }
        }
    }

    return N * M - answer;
}