문제

문제 분석

Naive한 방법은 트램펄린을 모든 영역에 대보고 개수를 세는 것이다. 이렇게하면 시간 복잡도가 O(NM)이 되고, 최대 50,000,000,000개의 위치가 가능한 것이기 때문에 불가능하다.

어떻게하면 더 효과적으로 셀 수 있을까? 고민했다.

별은 최대 100개밖에 되지 않기 때문에, 각 별을 기준으로 트램펄린 위치 후보를 만들면 되겠다고 생각했다.

처음에는 각 별을 포함하는 모든 트램펄린 위치를 계산해보려 했는데, 이 경우 시간 복잡도는 O(L^2 * K)로 상당히 크다.

다른 방법으로, 특정 하나의 별을 꼭짓점으로 하는 트램펄린이 최대가 되지 않을까 생각했다. 이 경우 트램펄린 위치 계산은 O(K)로 가능하다.

하지만 잘 생각해보면, 별이 꼭짓점일 때만 최대가 되는 것은 아니다.
정확히는, 특정 별이 트램펄린 모서리에 포함되기만 하면 되므로 여전히 O(L * K)의 계산이 필요하다.
여기에 별을 세는 비용 O(K)까지 더하면 전체 복잡도는 O(L * K^2)로 비효율적이다.

결국, 두 개의 별을 트램펄린의 모서리로 지정하면 가능한 트램펄린이 2개뿐이라는 점에 착안했다.
이 경우 별 쌍을 기준으로 트램펄린을 만들고, 그 안에 있는 별의 개수를 세면 된다.
이 방식의 전체 시간 복잡도는 O(K^2) * O(K) = O(K^3)이며, 현실적으로 가장 효율적인 방법이라고 판단했다.

알고리즘

maxCount = 0;
for ( 두 쌍 in stars){
	// case1
	boxPosLB = 두 쌍을 박스 모서리로 두도록
    tmpCount = CalculateStarsInBox(stars, boxPosLB);
    maxCount = max(maxCount, tmpcount);
    // case2
    boxPosLB = 두 쌍을 박스 모서리로 두도록
    tmpCount = CalculateStarsInBox(stars, boxPosLB);
    maxCount = max(maxCount, tmpcount);
    // case3
    // case4
}

자료구조

stars: vector<vec2> (K)

결과

성공

#include <iostream>
#include <vector>

using namespace std;

/*
world size: NxM
box size: LxL
Num of star : K
*/
int N, M, L, K;

struct vec2{
    int x;
    int y;
};

int CalculateStarsInBox( vector<vec2>& stars, vec2 boxPosLB );

inline int maxAB( int a, int b );
inline int minAB( int a, int b );

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M >> L >> K;

    vector<vec2> stars(K);
    for ( int i = 0; i < K; i++ )
        cin >> stars[i].x >> stars[i].y;

    int max_count = 0;

    for ( int i = 0; i < K; i++ ){
        for ( int j = i; j < K; j++ ){
            int temp_count = 0;
            vec2 boxPos = {0,0};
            vec2 LB = { minAB( stars[i].x, stars[j].x),
                    minAB( stars[i].y, stars[j].y ) };
            vec2 RT = { maxAB(stars[i].x, stars[j].x ),
                maxAB( stars[i].y, stars[j].y ) };

            // Case1
            boxPos.x = LB.x; boxPos.y = LB.y;
            temp_count = CalculateStarsInBox( stars, boxPos );
            max_count = maxAB(max_count, temp_count);
            // Case2
            boxPos.x = LB.x; boxPos.y = RT.y - L;
            temp_count = CalculateStarsInBox( stars, boxPos );
            max_count = maxAB(max_count, temp_count);
            // Case3
            boxPos.x = RT.x - L; boxPos.y = LB.y;
            temp_count = CalculateStarsInBox( stars, boxPos );
            max_count = maxAB(max_count, temp_count);
            // Case4
            boxPos.x = RT.x - L; boxPos.y = RT.y-L;
            temp_count = CalculateStarsInBox( stars, boxPos );
            max_count = maxAB(max_count, temp_count);
        }
    }

    cout << K - max_count << endl;
}

int CalculateStarsInBox( vector<vec2>& stars, vec2 boxPosLB )
{
    if ( boxPosLB.x < 0 )
        boxPosLB.x = 0;
    if ( boxPosLB.x + L > N)
        boxPosLB.x = N - L;
    if  (boxPosLB.y < 0 )
        boxPosLB.y = 0;
    if ( boxPosLB.y + L > M )
        boxPosLB.y = M - L;
    
    vec2 boxPosRT = { boxPosLB.x + L, boxPosLB.y + L };

    int count = 0;
    for ( int i = 0; i < K; i++ ){
        vec2 star = stars[i];

        if ( star.x < boxPosLB.x || boxPosRT.x < star.x )
            continue;
        if ( star.y < boxPosLB.y || boxPosRT.y < star.y )
            continue;
        //cout << "boxLB: " << boxPosLB.x << ", " <<  boxPosLB.y << endl;
        //cout << "star: " << star.x << ", " << star.y << endl;
        count++;
    }

    return count;
}

inline int maxAB( int a, int b )
{
    return a > b ? a: b;
}
inline int minAB( int a, int b )
{
    return a < b ? a : b;
}

Other

처음에 하나의 별을 꼭짓점으로 하는 트램펄린 개수가 O(k)밖에 되지 않는 것을 보고 바로 코드로 넘어가 버렸다. 다시 생각해보니 아닌 경우도 존재한다. 스스로 다른 예외 케이스를 떠올려 철저하게 검증하고 코드로 완성하는 습관을 들이자.