BOJ 22348(헬기 착륙장)풀이

solved.ac 티어 : 플5

 

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

22348번: 헬기 착륙장

이문제는 dp 문제있은데 dp인걸 알기 어렵다고 한다

이 문제는 빨강 페인트 a와 파랑 페인트 b 이렇게 두 개가 입력으로 들어오면 이 두 개의 양을 넘지 않는 선에서 만들 수 있는 모든 착륙장의 경우의 수를 출력하는 문제이다.

 

k개의 동심원인 착륙장을 만든다고 했을 때 k번째 동심원을 파랑 페인트를 칠한다고 하면 파랑 페인트는 b-k가 되고 남은 k-1개의 동심원은 a와 b-k만큼의 페인트로 칠해야 된다.

또는 k번째 동심원을 파랑 페인트로 칠하지 않는다고 했을때  파랑 페인트 양에는 변화가 없고 빨간색의 페인트는 a-k가 된고 k-1개의 동심원은 a-k, b만큼의 페인트로 칠해야 된다.

이 모든 걸 1,2,3,.... k번째 동심원까지 해줘야 된다.

이걸 2차원 배열로 나타 낼 수 있는데 dp [i][j]는 i번째 동심원일 때 파랑 페인트를 j만큼 썼을때의 경우의 수라고 정하자

그러면 dp[i][j]는 i번째 동심원일때 파랑 페인트를 쓰냐 안 쓰냐의 경우의 수를 더한 값이 된다.

즉 dp [i][j]=dp [i-1][j-i]+dp [i-1][j]가 된다.

이제 이렇게 dp 테이블을 만들어주고 문제의 첫 번째 예시 입력을 넣었을 때

i번째 동심원/파랑 페인트를 사용한 양	0	1	2	3	4	5	6
1	1	1	0	0	0	0	0
2	1	1	1	1	0	0	0
3	1	1	1	2	1	1	1

이런 테이블이 나온다. 

열은 파랑 페인트의 사용량이기 때문에 b를 넘어간 위치는 버린다.

또 파랑 페인트를 j만큼 썼을 때 남은 부분은 빨강 페인트로 칠했다는 것인데 나머지 부분이 a보다 많으면 안 되니 많은 부분도 버린다. 즉 i*(i+1)/2-j <=a인 부분만 사용한다(i는 동심원의 수, j는 파랑 페인트의 사용량)

이제 위 두 조건을 만족하는 부분을 모두 더해주면 빨강 페인트 a와 파랑 페인트 b가 있을 때 만들 수 있는 착륙장의 모든 경우의 수를 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=30;
ll MOD=1e9+7;
vector<ll>ch[502];
ll dp[502][50002];
vector<ll>st;
ll min(ll a,ll b){
    if(a>b)return b;
    else return a;
}
//최대 k 500
// 1부터 2,3,4,5... 순서대로 더했을때 50000을 넘지 않는 최대값은 49770이고 횟수는 315번
//dp[i][j]=i개의 동심원일때 파란색을 j만큼 썼을때의 가지수
int main(){
    st.push_back(0);
    ll cnt=0;
    for(int i=0;i<500;i++)st.push_back(st[i]+i+1);
    for(int i=1;i<501;i++){
        ll Q=min(50000,st[i])+1;
        ch[i].push_back(0);
        for(int g=0;g<Q;g++){
            if(i==1)dp[i][g]=1;
            else{
                dp[i][g]=dp[i-1][g];
                if(g>=i)dp[i][g]+=dp[i-1][g-i];
            }
            ch[i].push_back(ch[i][g]+dp[i][g]);
            dp[i][g]%=MOD;
        }
    }
    ll a,b,c;
    scanf("%lld",&a);
    for(int W=0;W<a;W++){
        scanf("%lld %lld",&b,&c);//빨,파
        ll i=1,ans=0;
        while(b+c>=st[i]){
            ll z=min(st[i],c)+1;
            if(z==st[i]-b)break;
            ans+=ch[i][z];
            if(st[i]>b){
                if(ch[i][st[i]-b+1]==0)break;
                ans-=ch[i][st[i]-b];
            }
            i++;
            ans%=MOD;
        }
        printf("%lld\n",ans%MOD);
    }
}