코딩테스트 -- 파괴되지 않은 건물 - (프로그래머스 / C++) / 누적합

프로그래머스

 

문제!

---

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

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

 

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

---

 

board에 공격과 회복스킬을 사용했을때 마지막까지 남아있는 건물의 갯수를 찾는 문제입니다!

 

 

어? 그냥 단순 for문으로 계속해주면 되지않을까...? 하는 마음으로 푸시면...

아래처럼 간단하게 나오지만

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    // skill = > [1이면 공격 2면 회복,x,y,x1,y1,세기]
    
    for(int i=0;i<skill.size();i++){
        if(skill[i][0]==1){
            skill[i][5]=skill[i][5]*(-1);
        }
        
        for(int a=skill[i][1];a<=skill[i][3];a++){
            for(int b=skill[i][2];b<=skill[i][4];b++){
                board[a][b]+=skill[i][5];
            }
        }
    }
    
    for(int i=0;i<board.size();i++){
        for(int j=0;j<board[i].size();j++){
            if(board[i][j]>0){
                answer+=1;
            }
        }
    }
    
    return answer;
}

효율성에서 0점...

 

다른 방법을 생각해봅시다!

 

 1차원배열로도 바꾸어 보았지만... 차이가 있는방법이 아니였고...

새로운 배열에 모든 공격,스킬을 계산하고 마지막 연산하는 방법도... 빠르지 않았습닏다..

 

 

결국 찾아보았습니다! 정답은 누적합!

 

누적합 문제를 풀어본 기억이 있는데 이 문제에 적용이 될 줄은 상상도 못했습니다;;

 

 

누적합이란?

 

현재부터 마지막 까지의 합들을 좀더 빠르게 계산할수있는 방법으로

아래의 예시를 보며 이해해 보겠습니다.

 

2차원으로 하기전 1차원으로 생각해보았을때

기본배열 : [1,2,3,4,5] 

문제 : 2~3 까지 2를 빼주겠다!  , 0~2 까지 4를 빼주겠다! 

 

가장 먼저 누적합을 저장할 새로운 배열을 만들어 줍니다.

[0,0,0,0,0]

여기다가 이제 차들을 저장할텐데

 

먼저 2~3 까지 2를 빼주겠다를

[0,0,-2,0,2] 이렇게  저장할수있습니다!  >> 이상태로 누적합 실시시 [0,0,-2,-2,0] 이런식으로 변경됨!

 

그리고 이어서 0~2 까지 4를 빼주겠다는

[-4,0,-2,4,2] 이렇게 만들어 지게 됩니다. 

 

여기서 누적합!

여긴 1차원 배열이기에 한쪽에서 다른 한쪽으로 값을 전달해주면?

[-4, (0 - 4), (-2 - 4), (4 - 6), (2 - 2)] 이렇게 변경가능합니다!

 

>>[-4,-4,-6,-2,0] 이렇게! 차들의 합으로 나타낼수 있습니다 

 

이걸 원래 [1,2,3,4,5] 와 합쳐준다면 문제를 좀더 빠르게! 해결할수있는 방법이 누적합 방법입니다.

 

약간 범위를 정해놓고? 한번에 연산한다는 점에서 일반 for문보다 훨씬 빠르다는 것을 알 수 있습니다.

 

 

1차원 배열에서는 해결해 보았고 2차원배열에서는?

똑같습니다. 범위를 지정해주고 마지막에 스킬과 공격의 합을 연산해주는 방법을 이용하면 됩니다!

 

 

다시 시작!

 

새로운 attack 벡터에 누적합 범위를 넣어 줍시다.

    int board_X=board[0].size(); //가로
    int board_Y=board.size(); //세로 board[board_Y][board_X]
    
    vector<vector<int>> attack(board_Y+1,vector<int>(board_X+1));
    
    for(int i=0;i<skill.size();i++){//누적합 범위 만들기
        if(skill[i][0]==1){
            skill[i][5]=skill[i][5]*(-1);
        }
        attack[skill[i][1]][skill[i][2]]+=skill[i][5]; //시작위치
        attack[skill[i][3]+1][skill[i][2]]-=skill[i][5]; // 시작위치로부터 오른쪽
        attack[skill[i][1]][skill[i][4]+1]-=skill[i][5]; // 시작위치로부터 아래
        attack[skill[i][3]+1][skill[i][4]+1]+=skill[i][5]; // 시작위치로부터 대각선
        
    }

[4,0,0,-4]

[0,0,0,0]

[-4,0,0,4]

 

이런식으로 사각 범위를 만들어 주는것!

 

범위를 만들어 주었으면 이제 세로로 합을 계산해주고 가로로도 계산해줍시다.

int memo=0;
    
    //세로 누적합
   
    for(int i=0;i<board_X;i++){
        memo=0;
        for(int j=0;j<board_Y;j++){
            attack[j][i]+=memo;
            memo=attack[j][i];
        }
    }
    
    //가로 누적합
    for(int i=0;i<board_Y;i++){
        memo=0;
        for(int j=0;j<board_X;j++){
            attack[i][j]+=memo;
            memo=attack[i][j];
        }
    }

 

 

그 후 건물이 남아있는지 확인하면 끝!

//합
    for(int i=0;i<board_Y;i++){
        for(int j=0;j<board_X;j++){
            if(board[i][j]+attack[i][j]>0){
                answer+=1;
            }
        }
    }

 

 

 

 

누적합이라는 개념을 알고있어야 풀수있는 문제였네요.... 오래걸렸습니다 ㅠ

 

누적합은 다시한번 공부 해보겠습니다!

 

 

ALL

#include <string>
#include <vector>
using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int memo=0;
    // skill = > [1이면 공격 2면 회복,x,y,x1,y1,세기]
    
    int board_X=board[0].size(); //가로
    int board_Y=board.size(); //세로 board[board_Y][board_X]
    vector<vector<int>> attack(board_Y+1,vector<int>(board_X+1));
    
    for(int i=0;i<skill.size();i++){//누적합 범위 만들기
        if(skill[i][0]==1){
            skill[i][5]=skill[i][5]*(-1);
        }
        attack[skill[i][1]][skill[i][2]]+=skill[i][5];
        attack[skill[i][3]+1][skill[i][2]]-=skill[i][5];
        attack[skill[i][1]][skill[i][4]+1]-=skill[i][5];
        attack[skill[i][3]+1][skill[i][4]+1]+=skill[i][5];
        
    }
    
    //세로 누적합
    for(int i=0;i<board_X;i++){
        memo=0;
        for(int j=0;j<board_Y;j++){
            attack[j][i]+=memo;
            memo=attack[j][i];
        }
    }
    //가로 누적합
    for(int i=0;i<board_Y;i++){
        memo=0;
        for(int j=0;j<board_X;j++){
            attack[i][j]+=memo;
            memo=attack[i][j];
        }
    }
    
    //합
    for(int i=0;i<board_Y;i++){
        for(int j=0;j<board_X;j++){
            if(board[i][j]+attack[i][j]>0){
                answer+=1;
            }
        }
    }

    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!