파괴되지 않은 건물 바로가기
이번 문제는 정답을 보고 풀었다.
정답 사이트에 굉장히 친절히 설명을 해주어서 정답 레퍼런스만 보고도 풀수 있었다.
애초에 누적합이라는 알고리즘을 몰랐기에, 이번기회를 통해서 더 잘알게 되었다.
누적합에 대한 알고리즘은 나중에 다시 설명하도록 하고 여기서 핵심은
만약 배열이
ㅁㅁㅁ
ㅁㅁㅁ
ㅁㅁㅁ
이렇게 구성되어있고 1,1 부터 2,2까지 +2를 해주고싶다면
ㅁㅁㅁㅁ
ㅁㅁㅁㅁ
ㅁㅁㅁㅁ
ㅁㅁㅁㅁ
한칸 더큰 누적합 배열을 만들고
1,1 2,2 좌표 변경을 해주고(배열 1칸이 늘어났으니까) 2,2 3,3
1,1 -> 2
3,1 -> -2
3,3 -> 2
1,3 -> -2
해주는것이다.
ㅁㅁㅁㅁ
ㅁ2ㅁ-2
ㅁㅁㅁㅁ
ㅁ-2ㅁ2
그다음에 왼->오로 누적합 위->아래로 누적합을해주면
ㅁㅁㅁㅁ
ㅁ220
ㅁ220
ㅁ000
이런식으로 되는데
그러고 이제
ㅁㅁㅁ
ㅁ22
ㅁ22
로 다시 짜른다음에
이걸 원래 배열과 합치면 된다
공식
- x,y a,b => 각 좌표를 +1해준다.
- 1칸 크기가 더큰 배열을 만든다.
- [x1-1][y1-1] += degree;
[x2][y1-1] += -degree;
[x2][y2] += degree;
[x1-1][y2] += -degree; - 누적합해주기
이렇게 누적합에 대해서 넘어가고,
누적합이 뭔지는 알았는데 왜써야하는지부터 생각해보자.
애초에 정확성과 효율성이 나눠져 있다고 하지만, 문제를 읽으면서 내용파악을 하다가 제한조건으로가서 n값을 보자 일단 보드의 크기가 1000 바이 1000이고 skill 횟수가 250,000번이다.
이러면 뭔가 이상하다 낌새를 눈치채야한다.
만약 이런식으로 크게 주어지지 않더라도, 항상 문제를 이해하고 대충 로직을 짜보면서 n값을 넣어서 로직을 구현하기전에 내가 짠 로직이 시간복잡도 내에 해결할 수 있는지 확인해보고 구현해야한다.
일단 만약에 최대로 0,0부터 999,999까지 +1하는 skill을 250,000번 한다고 치자 만약에 이중포문으로 돌면
999^2250,000번일 것이다. 대충봐도 이렇게는 절대로 시간복잡도 내에 풀수가 없다.
그러니까 한마디로 O(NM*250,000)으로는 문제를 풀수가 없다는말이다. 이걸 줄이기 위해서 누적합을 이용한다.
for(int i=0;i<skill.size();i++){
int type = skill[i][0];
int x1 = skill[i][1]+1;
int y1 = skill[i][2]+1;
int x2 = skill[i][3]+1;
int y2 = skill[i][4]+1;
int degree = skill[i][5];
if(type == 1) degree = -degree;
addmap[x1-1][y1-1] += degree;
addmap[x2][y1-1] += -degree;
addmap[x2][y2] += degree;
addmap[x1-1][y2] += -degree;
}skill을 for문으로 돌면서 addmap에다가 누적합 공식대로 넣어준다.
for(int i=0;i<1000;i++){
for(int j=0;j<1000;j++){
addmap[i][j+1]+=addmap[i][j];
}
}
for(int i=0;i<1000;i++){
for(int j=0;j<1000;j++){
addmap[i+1][j]+=addmap[i][j];
}
}왼->오, 위->아래로 누적합을 해준다.
for(int i=1;i<=M;i++){
for(int j=1;j<=N;j++){
map[i][j]+=addmap[i-1][j-1];
}
}addmap의 맨 끄트머리 뺴고 addmap의 0부터 시작해서 더해준다.
그리고 무너지지 않은 건물을 파악한다.
for(int i=1;i<=M;i++){
for(int j=1; j<=N;j++){
if(map[i][j]>0) answer++;
}
}정답코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
long long map[1001][1001];
long long addmap[1001][1001];
int M = 0;
int N = 0;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
M=board.size();
N=board[0].size();
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
map[i+1][j+1]=board[i][j];
}
}
for(int i=0;i<skill.size();i++){
int type = skill[i][0];
int x1 = skill[i][1]+1;
int y1 = skill[i][2]+1;
int x2 = skill[i][3]+1;
int y2 = skill[i][4]+1;
int degree = skill[i][5];
if(type == 1) degree = -degree;
addmap[x1-1][y1-1] += degree;
addmap[x2][y1-1] += -degree;
addmap[x2][y2] += degree;
addmap[x1-1][y2] += -degree;
}
for(int i=0;i<1000;i++){
for(int j=0;j<1000;j++){
addmap[i][j+1]+=addmap[i][j];
}
}
for(int i=0;i<1000;i++){
for(int j=0;j<1000;j++){
addmap[i+1][j]+=addmap[i][j];
}
}
for(int i=1;i<=M;i++){
for(int j=1;j<=N;j++){
map[i][j]+=addmap[i-1][j-1];
}
}
for(int i=1;i<=M;i++){
for(int j=1; j<=N;j++){
if(map[i][j]>0) answer++;
}
}
return answer;
}알고보니까 누적합의 대표적인 문제였다.
핵심은 행렬의 index접근과 같이 전부다 for문을 돌면서 접근할 수 없을때 사용하는 알고리즘이었다.
DP와 같은 문제에서도 활용되는거 같아. 다음 문제는 누적합 문제를 한번 더 풀어보도록 하겠다.
