2022 카카오 블라인드 코딩테스트 6번

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

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

2022 카카오 블라인드 코딩테스트 6번

작년에 인턴쉽문제를 풀었을때 누적합 문제가 있어서 조금 깊게 공부했는데

누적합의 확장인 imos법이라는게 있었음 

시간복잡도도 좋고, 풀이법도 간단하여 기억하고 있었는데 딱 적용시킬 수 있는 문제라고 생각됨

아래 참고

https://imoz.jp/algorithms/imos_method.html

いもす法

#include <string>
#include <vector>
#define MAX 1004
using namespace std;
int arr[MAX][MAX];

int max(int a, int b) {
	return a > b ? a : b;
}

int imos(vector<vector<int>> board, vector<vector<int>> skill) {
	//set damage
	for (auto index : skill) {
		//index[0] = type
		//index[1] = fy
		//index[2] = fx
		//index[3] = sy
		//index[4] = sx
		//index[5] = damage
		int type = 1;
		if (index[0] == 1)
			type *= (-1);

		arr[index[1]][index[2]] += index[5] * type;
		arr[index[3] + 1][index[4] + 1] += index[5] * type;
		arr[index[1]][index[4] + 1] -= index[5] * type;
		arr[index[3] + 1][index[2]] -= index[5] * type;

	}
	//damage 배열 계산
	for (int i = 1; i < board.size(); i++) {
		for (int j = 0; j < board[i].size(); j++) {
			arr[i][j] += arr[i - 1][j];
		}
	}
	for (int i = 0; i < board.size(); i++) {
		for (int j = 1; j < board[i].size(); j++) {
			arr[i][j] += arr[i][j - 1];
		}
	}

	//기존 건물값에 damage 계산
	for (int i = 0; i < board.size(); i++) {
		for (int j = 0; j < board[i].size(); j++) {
			arr[i][j] += board[i][j];
		}
	}

	//파괴된 건물 계산
	int cnt = 0;
	for (int i = 0; i < board.size(); i++) {
		for (int j = 0; j < board[i].size(); j++) {
			if (arr[i][j] >0)
				cnt++;
		}
	}
	return cnt;


}

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
	int answer = imos(board, skill);
	return answer;
}

아이디어

imos알고리즘을 그대로 사용했음