[프로그래머스/Level 3/C++/2022 카카오 블라인드 채용] 파괴되지 않은 건물

https://school.programmers.co.kr/learn/courses/30/lessons/92344

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

 

- 예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

- 최종적으로 총 10개의 건물이 파괴되지 않았습니다.

 

[문제 조건]

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 100
• 1 ≤ board의 열의 길이 (= M) ≤ 100
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
• 1 ≤ skill의 행의 길이 ≤ 100
  • 1 ≤ degree ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

[문제 풀이]

아마 대부분의 사람들이 문제를 읽고 난 뒤에 직감적으로 "skill마다 board를 갱신하면 시간초과가 걸리지 않을까.....?" 라는 생각을 할 것이다.

 

물론 필자도 위와 같은 생각을 했다.

 

그렇다면 다른 방법을 통해 board를 한꺼번에 갱신시켜줘야 한다는 것이다.

 

한꺼번에 갱신하기 위해서는 skill별 데미지를 누적해서 board를 한꺼번에 바꿔주는 수 밖에 없다는 것이다. 따라서 이 문제는 누적합을 이용해 풀어볼 것이다.

 

아이디어는 다음과 같다. 예를들어 (2,2)라는 위치에 [-4, 50, -30, 40] 와 같은 데미지와 회복이 들어왔다고 가정해보자. 과정을 하나씩 보면 -4의 데미지, 50의 회복, -30의 데미지, 40의 회복이 이루어졌다. 

하지만 결과만 놓고보면 56의 회복이 들어온 것과 동일한 결과가 나온다.

 

이러한 아이디어를 이용해 2차원 배열에 한번 적용시켜보자.

예를들어 다음과 같은 표에 (0,0) ~ (2,2)까지에 n만큼의 변화가 일어났다고 가정해보자.

 

여기서 색칠된 부분을 각 skill마다 n으로 채우는 것이 아니라 색칠된 부분은 n만큼 변화가 있다고 표시만 해두고 모든 skill에 대한 작업이 끝났을때 한꺼번에 합들을 바꿔줄 것이다.

 

먼저 (r1, c1) ~ (r2, c2) 에 n만큼의 변화가 있으면 첫번째 표와 같이 값을 더해준다.

sum[r1][c1] += n , sum[r2+1][c2+1] += n , sum[r2+1][c1] += -n , sum[r1][c2+1] += -n

 

그 다음 각 행 별로 왼쪽의 값을 오른쪽에 더해준다. ( 두번째 표 참고 )

그 다음 각 열 별로 위의 값을 아래에 더해준다. ( 세번째 표 참고 )

 

결과 적으로 주황색부분에 모두 n만큼의 변화가 일어난 것을 볼 수 있다.

 

하지만 두번째 표와 세번째 표의 과정은 모든 skill에 대해 첫번째  표의 과정을 다 마친 후 수행해야 올바르게 동작을 한다. 왜냐하면 각 과정에 대해 위의 순서를 모두 적용시키면 맨 처음에 직감적으로 들었던 생각과 다를바가 없는 방법이다.

 

 

[소스 코드]

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

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int n = board.size();
    int m = board[0].size();
    vector<vector<int>> sum;
    sum.resize(n+1);
    for(int i=0; i<n+1; i++)
        sum[i].resize(m+1);
    
    for(int i=0; i<skill.size(); i++)
    {
        int y1 = skill[i][1]; int x1 = skill[i][2];
        int y2 = skill[i][3]; int x2 = skill[i][4];
        int degree = skill[i][5];
        
        if(skill[i][0] == 2) degree = -1 * degree;
        
        sum[y1][x1] += degree;
        sum[y2+1][x2+1] += degree;
        sum[y2+1][x1] += -degree;
        sum[y1][x2+1] += -degree;
    }
        
    for(int i=0; i<n+1; i++)
        for(int j=0; j<m; j++)
            sum[i][j+1] += sum[i][j];
    
    for(int i=0; i<m+1; i++)
        for(int j=0; j<n; j++)
            sum[j+1][i] += sum[j][i];
    
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(board[i][j] - sum[i][j] >= 1) answer++;
    
    return answer;
}

누적합 기술을 은근 써먹을데가 많을 것 같다

굳