[C++/프로그래머스] 파괴되지 않은 건물

문제

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

코딩테스트 연습 - 파괴되지 않은 건물

문제가 길다.. 

요약하면, 

 

NxM의 초기 borad에서 (r1, c1) ~(r2, c2)의 임의의 구간?부분을 공격(-)했다가 회복(+)했다가 하면서 

최종적으로 값이 0보다 큰 칸의 갯수를 세면 되는 문제이다.

풀이

지난주 스터디시간에 들었던 IMOS법을 이용해보았다.

IMOS법이란? <- 이 블로그에 아주 설명이 잘 되어 있다.

 

N+1 x M+1 크기의 cache배열을 만들어서 imos법을 이용해 공격, 회복 로그?를 기록하고

맨 마지막에 가로로 한번, 세로로 한번 쭉 훑어 최종적인 cache배열 값을 구한다. 

그리고, cache[r][c] + board[r][c] > 0 인 칸들의 갯수를 세어주면 된다.

 

이런 느낌의 (완전탐색으로하면 시간초과날거같은) 문제를 그동안 매우 어려워했는데, imos법을 알게되었으니 풀 수 있는 문제가 늘어날 것 같다.

 

* imos를 아이모스가 아니라, 이모스라고 읽는 것 같다 (일본어인듯?)

코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> cache;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int N = board.size();
    int M = board[0].size();
    cache = vector<vector<int>>(N+1, vector<int>(M+1, 0)); // imos위해 하나씩 크게 만들기
    for (auto s: skill) {
        int degree = s[5];
        int r1 = s[1]; int c1 = s[2];
        int r2 = s[3]; int c2 = s[4];
        if (s[0] == 2) { // 공격
            cache[r1][c1] += degree;
            cache[r1][c2+1] -= degree;
            cache[r2+1][c1] -= degree;
            cache[r2+1][c2+1] += degree;
        } else { // 회복
            cache[r1][c1] -= degree;
            cache[r1][c2+1] += degree;
            cache[r2+1][c1] += degree;
            cache[r2+1][c2+1] -= degree;
        }
    }
    // 가로로 휩쓸기
    for (int r=0;r<N;r++) {
        int sum = cache[r][0];
        for (int c=1;c<M;c++) {
            cache[r][c] += sum;
            sum = cache[r][c];
        }
    }
    // 세로로 휩쓸기
    for (int c=0;c<M;c++) {
        int sum = cache[0][c];
        for (int r=1;r<N;r++) {
            cache[r][c] += sum;
            sum = cache[r][c];
        }
    }
    
    for (int r=0;r<N;r++) {
        for (int c=0;c<M;c++) {
            if (cache[r][c] + board[r][c] > 0) answer++;
        }
    }
    return answer;
}

결과