Programmers - 파괴되지 않은 건물

---

title: Programmers - 파괴되지 않은 건물
date: 2022-10-18
tags:

• Algorithm
• DP

---

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

문제 요약

2차원의 행렬에 주어진 명령을 수행하여 값을 변경한다.
명령은 작은 직사각형 구간이 주어지며, 해당 구간의 값을 일정 수치만큼 내리거나 높인다.
모든 명령을 시행한 후, 값이 1 이상이 되는 것들의 개수를 구하여 return한다.

문제 풀이

행렬이 최대 크기일 때 1M개의 셀이 존재하며, 명령은 최대 250K이다.
최대 크기만큼의 명령이 최대 개수만큼 주어질 경우, 모든 셀에 작업을 해준다면 250G라는 말도 안 되는 수치가 나온다.
처음에는 이 부분을 신경쓰지 않고 모든 셀에 적용하였다가, 효율성 테스트에서 TLE가 발생하였다.
DP를 적용하여 이 문제를 해결하였다.


모든 셀에 적용하기 전에, 직사각형의 시작 위치(주어진 좌측 상단의 점)에 변화량을 기록한다.
한쪽 꼭지점을 향하는 누적합 방식을 이용하면 이 변화량이 각 셀의 변화량으로 바뀐다.
하지만 이렇게 적용하면 경계선 없이 마지막 셀까지 전부 적용이 되어 이를 해결할 수 없다.
그렇기에 또 하나의 명령이 주어진 것처럼 범위를 벗어나는 부분에 이를 상쇄할 변화량을 추가한다.

Sample

이해를 돕기 위해 그림을 가져왔다. 명령은 빨간 사각형에 1을 더하는 것이다.
(0,0)에 1을 기록한다. 이로 인하여 전체 사각형에 1씩 적용이 될 것이다.
(0,j1), 즉 우측 파란 사각형의 시작 부분에 -1을 기록한다. 빨간 사각형과 그 하단의 파란 사각형은 1씩 더해지며, 우측의 사각형은 값이 유지된다.
(i1,0), 좌측 파란 사각형의 시작 부분에 동일하게 -1을 기록한다. 빨간 사각형은 1이 더해지며, 노란 사각형은 -1이 더해진다.
마지막으로 (i1,j1)에 1을 기록하면 빨간 사각형에만 1이 더해진다.


간단히, 명령에서 주어진 사각형의 첫 위치, 그리고 끝 위치의 대각선 한 칸 위치에 주어진 변화량을, 우상단과 좌하단 바로 옆에 있는 위치에 - 변화량을 기록하면 된다.
범위를 벗어날 경우, - 변화량을 기록할 범위가 아예 존재하지 않는다는 뜻이므로 무시하면 된다.


이 문제는 아마 작년 Blind 채용의 2번 혹은 3번 문제일 것이라 추측한다.
정확성 테스트는 누구나 통과할 수 있으며, 위 풀이처럼 전체 셀을 순회하는 무식한 방법에서 개선해야 효율성 테스트를 통과할 수 있다.
알고리즘에 대한 이해도, 그리고 이를 응용하여 효율성 테스트를 해결할 수 있는지에 대한 문제이다.

프로그램

#include <vector>

using std :: vector ;

int solution ( vector < vector < int > > board , vector < vector < int > > skill )
{
    int answer = 0 ;
    int iHeight = board.size () ;
    int iWidth = board [ 0 ].size () ;
    int iSkillSize = skill.size () ;
    vector < vector < int > > vDP ( iHeight , ( vector < int > ( iWidth , 0 ) ) ) ;



    for ( int i = 0 ; i < iSkillSize ; ++i )
    {
        int iDamage = 2 == skill [ i ] [ 0 ] ? 1 : -1 ;
        int iX1 = skill [ i ] [ 1 ] ;
        int iY1 = skill [ i ] [ 2 ] ;
        int iX2 = skill [ i ] [ 3 ] ;
        int iY2 = skill [ i ] [ 4 ] ;
        iDamage *= skill [ i ] [ 5 ] ;

        vDP [ iX1 ] [ iY1 ] += iDamage ;

        if ( iX2 + 1 < iHeight )
            vDP [ iX2 + 1 ] [ iY1 ] -= iDamage ;
        if ( iY2 + 1 < iWidth )
            vDP [ iX1 ] [ iY2 + 1 ] -= iDamage ;
        if ( ( iX2 + 1 < iHeight ) && ( iY2 + 1 < iWidth ) )
            vDP [ iX2 + 1 ] [ iY2 + 1 ] += iDamage ;
    }

    // Sum to right
    for ( int i = 0 ; i < iHeight ; ++i )
    {
        for ( int j = 1 ; j < iWidth ; ++j )
        {
            vDP [ i ] [ j ] += vDP [ i ] [ j - 1 ] ;
        }
    }
    // Sum to Down
    for ( int j = 0 ; j < iWidth ; ++j )
    {
        for ( int i = 1 ; i < iHeight ; ++i )
        {
            vDP [ i ] [ j ] += vDP [ i - 1 ] [ j ] ;
        }
    }

    // Sum to right
    for ( int i = 0 ; i < iHeight ; ++i )
    {
        for ( int j = 0 ; j < iWidth ; ++j )
        {
            if ( 0 < board [ i ] [ j ] + vDP [ i ] [ j ] )
                ++ answer ;
        }
    }


    return answer ;
}