[백준 22348] 헬기 착륙장

1. 풀이

DP로 푼 풀이가 많지만, 대회 때 점화식이 전혀 생각나지 않아서 구간합으로 해결했다.

\(r=1,2,3\) 반지름인 원을 만드는 경우의 수를 잘 관찰해보면 총 $2r$개의 경우의 수를 가진다.

\(r=1:(0,1),(1,0)\)

\(r=2:(2,1),(0,3),(3,0),(1,2)\)

\(r=3:(5,1),(3,3),(6,0),(3,3),(4,2),(1,5)\)

나열을 해보면 규칙을 찾아볼 수 있다. \(r−1\)의 쌍 \((a,b)\)에서 \((a+r,b)\;or\;(a,b+r)\)으로 새로 생긴다. 여기서 \(a\)가 되는 숫자의 개수를 관찰해보자.

\(r=1:a=0,1\)

\(r=2:a=0,1,2,3\)

\(r=3:a=0,1,2,3,3,4,5,6\)

이전 \(a\)에서 \(r\)을 더해준 형태로 진행된다. 각 숫자들이 몇 번 나타나는 지에 대해 구간합을 만들어줄 수 있다. 그리고 \(b\)는 \(\frac{r(r+1)}{2}−a\)이다.

그렇다면 현재가지고 있는 \(a,b\)로 반지름 \(r\)마다 어느 숫자까지 만들 수 있는 구간(\(a:0 \sim u, b:v \sim \frac{r(r+1)}{2}\))이 나온다. 그러므로 두 구간이 동시에 포함된 부분은 곧 \(r\)에서 만들 수 있는 경우의 수가 된다.

\(r≤450\)이므로 구간합을 \(O(450^3)\)에 만들어 줄 수 있고, 쿼리 당 \(O(450)\)에 해결할 수 있다.

2. 소스코드

#include <bits/stdc++.h>


using namespace std;


typedef long long ll;
const ll mod = 1e9 + 7;


const ll MAX = 450;


ll psum[MAX + 1][MAX * MAX + 1];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);


    psum[1][0] = psum[1][1] = 1;
    for (int i = 2; i <= MAX; i++) {
        int sz = i * (i + 1) / 2;
        for (int j = 0; j <= sz; j++) {
            psum[i][j] = (psum[i][j] + psum[i - 1][j])%mod;
            psum[i][j + i] = (psum[i][j+i]+psum[i - 1][j])%mod;
        }
    }


    for (int i = 1; i <= MAX; i++)
        for (int j = 1; j <= MAX*MAX; j++)
            psum[i][j] = (psum[i][j] + psum[i][j - 1]) % mod;


    int tc; cin >> tc;
    while (tc--) {
        int a, b; cin >> a >> b;
        if (a > b) swap(a, b);


        ll ans = 0;
        for (int i = 1; i <= MAX; i++) {
            ll sz = i * (i + 1) / 2;
            ll to = sz - b - 1;
            if (a < to) break;
            ll diff = psum[i][a];
            if (to >= 0) diff -= psum[i][to];
            ans = (ans + diff+mod) % mod;
        }


        cout << ans << "\n";
    }


    return 0;
}