헬기 착륙장( BOJ 22348 )

문제 : https://www.acmicpc.net/problem/22348

22348번: 헬기 착륙장

 

문제 파악하기

2개의 페인트통을 사용해서 헬기 착륙장을 그릴 수 있는 경우의 수를 구하는 문제입니다. 헬기 착륙장은 반지름이 서로 다른 원으로 구성되어 있으며, 반지름이 1부터 R까지 1씩 차이나게 그릴 수 있습니다. 하나의 헬기 착륙장은 항상 하나의 색으로만 만들 수 있으며, 각각의 페인트통이 최대 50,000개 있기 때문에 그릴 수 있는 헬기착륙장의 최대 크기는 대략 450입니다. 따라서, 우리는 450개의 헬기착륙장 중 몇 개를 그릴 수 있는지 확인하면 됩니다.

 

문제 해결하기

떠올릴 수 있는 가장 간단한 방법은 2차원 배열을 사용하여 입력되는 쿼리마다 동적 프로그래밍을 하는 방법입니다. 현재 헬기 착륙장의 반지름을 r, 지금까지 사용한 빨간 페인트통의 양을 red라고 하면 우리는 다음과 같이 점화식을 세울 수 있습니다.

dp[r][red] = dp[r-1][red] + dp[r-1][red-r]

 

위의 점화식에서 주의할 점은 dp[r-1][red]의 값을 참조하기 위해서는 파란 페인트통의 개수가 r만큼 있어야 합니다. 그럼 파란 페인트통의 개수는 어떻게 구할 수 있을까요? 우리에게 주어진 정보를 활용하면 쉽게 구할 수 있습니다. 우선, 지금까지 (r-1) 크기의 착륙장을 그렸습니다. 헬기 착륙장은 항상 크기가 1부터 하나씩 증가하며, (r-1) 크기의 헬기 착륙장까지 그렸다면 사용한 전체 페인트통의 양은 (r-1)*r/2가 됩니다. 그리고 지금까지 사용한 빨간 페인트의 양은 red이므로 지금까지 사용한 파란통의 양은 (r-1)*r/2 - red 가 됩니다. 그렇기에 우리는 파란 페인트 통의 양을 계산한 다음, 탐색을 진행할 수 있는지 여부에 따라 dp 값을 구해주면 문제의 해답을 구할 수 있습니다.

 

다만, 이와 같은 경우로 프로그래밍 시 90점만 맞게 됩니다. 쿼리의 개수가 10,000개이며, 각각의 쿼리에 대해 450*50000 배열의 값을 탐색하기에 1초라는 시간은 너무도 짧습니다. 그렇기에 우리는 먼저 dp 배열을 구해서 쿼리를 빠르게 처리해야 합니다. 다행히 빨간 페인트통의 개수에 따라 그릴 수 있는 헬기 착륙장의 경우의 수는 정해져있기에 위에서 정의한 dp 배열의 값을 우선 채워넣은 다음에 쿼리를 계산하면 됩니다.

 

쿼리를 계산할 때에는 빨간 페인트 기준으로 사용해야하는 최솟값과 최댓값이 있습니다. 만약 현재 원의 크기가 1부터 지금(r)까지 파란 페인트통으로 전부 그릴 수 있다면 빨간 페인트를 하나도 사용하지 않아도 됩니다. 하지만 파란 페인트통의 개수가 부족하다면 빨간 페인트통은 ( (r까지 그리는데 필요한 페인트 양) - 파란 페인트 통의 양 )만큼은 무조건 사용해야 합니다. 빨간 페인트통을 최대로 사용하는 범위는 반대로 구할 수 있습니다. 만약 지금(r)까지 빨간 페인트통으로 전부 그릴 수 있다면 r*(r+1)/2만큼 사용할 수 있지만, 만약 빨간 페인트통이 부족하다면 전체 빨간 페인트통의 양만큼까지 사용할 수 있습니다. 이렇게 원의 크기에 따라 최솟값과 최댓값을 구해놓고, 해당 범위 내의 경우의 수를 모두 더해주면 문제를 풀 수 있습니다. 물론, 누적합을 미리 구해놓으면 원의 크기에 따라 O(1)만에 값을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#define RMAX 450
#define VMAX 50010
#define MOD 1000000007
#define lint long long int
 
int T, red, blue;
lint dp[RMAX][VMAX], dpSum[RMAX][VMAX];
 
lint ret;
int vmin, vmax, tot;
 
int main() {
    dp[0][0] = 1;
    for(int r=1;r<RMAX;r++) {
        for(int v=0;v<VMAX;v++) {
            dp[r][v] = dp[r-1][v];
            if(v-r>=0) dp[r][v] = (dp[r][v]+dp[r-1][v-r])%MOD;
            
            if(v == 0) dpSum[r][v] = dp[r][v];
            else dpSum[r][v] = (dpSum[r][v-1] + dp[r][v])%MOD;
        }
    }
    
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &red, &blue);
        
        ret = 0;
        for(int r=1;r*(r+1)/2<=(red+blue);r++) {
            tot = r*(r+1)/2;
            vmin = tot<blue ? 0:tot-blue;
            vmax = tot<red ? tot:red;
            
            if(vmin == 0) ret = (ret+dpSum[r][vmax])%MOD;
            else ret = (ret + dpSum[r][vmax]-dpSum[r][vmin-1] + MOD)%MOD;
        }
        
        printf("%lld\n", ret);
    }
}

후기

미리 값을 구해놓고 할용할 수 있다는 점을 떠올리는데 오래 걸렸던 문제입니다. 딱히 알고리즘 기법이라는 게 없는 문제로, 전형적인 동적 프로그래밍 문제라는 생각이 듭니다. 문제를 추상화하는데 조금은 어려웠지만 재미있는 문제였습니다.