[Algorithm] Programmers :: 파괴되지 않은 건물

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

프로그래머스

int dp[1001][1001] = { 0 };
 
int solution(vector<vector<int>> board, vector<vector<int>> skill) 
{
    int answer = 0;
 
    for (int i = 0; i < skill.size(); ++i)
    {
        int startY = skill[i][1];
        int startX = skill[i][2];
        int destY = skill[i][3];
        int destX = skill[i][4];
        int damage = skill[i][0] == 1 ? skill[i][5] * -1 : skill[i][5];
 
        dp[startY][startX] += damage;
        dp[destY + 1][startX] += damage * -1;
        dp[startY][destX + 1] += damage * -1;
        dp[destY + 1][destX + 1] += damage;
    }
 
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[0].size(); ++j)
        {
            dp[i][j + 1] += dp[i][j];
        }
    }
 
    for (int i = 0; i < board[0].size(); ++i)
    {
        for (int j = 0; j < board.size(); ++j)
        {
            dp[j+1][i] += dp[j][i];
        }
    }
 
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[0].size(); ++j)
        {
            if (board[i][j] + dp[i][j] >= 1)
            {
                ++answer;
            }
        }
    }
 
    return answer;
}

이 문제의 1차원버전을 예전에 풀었었는데 기억을 못했다..

일단 완전탐색으로는 당연히 못푼다. 1000 * 1000 * 250000 정도의 횟수가 발생하기 때문이다.

 

해결하기 위해서는 누적합을 이용한다. 일단 기본적으로 생각나는 누적합은 0,0을 기준으로 n,n까지의 합을 각 인덱스에 다 저장한다음 특정 (a,a) ~ (b,b)까지의 구간합을 구하는 문제가 생각날 텐데 이 문제에서의 누적합은 이게 아니다.

 

1차원기준으로 설명을 하자면 그저 skill의 시작인덱스 s에 데미지를 명시하고 끝인덱스가 d일경우 d+1에 데미지 * -1을 명시한다. 

이렇게 명시만 해놓으면 된다. skill갯수만큼 명시한다음, 맨 나중에 합을 누적시켜준다음 board값이랑 합쳐만 주면 된다!

그러면 시간복잡도는 압도적으로 줄어든다. 스킬갯수만큼 표시를 해두고 나중에 board순회를 세번만 해주면 끝이다.

 

자세한 설명은 카카오 문제해설링크를 참고하면 된다.

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설