2021년 정올 본선 1번 헬기 착륙장

최대 반지름이 n인 원을 그리려면 페인트의 색깔과 관계없이 고정적으로 1부터 n까지의 합((n + 1)n / 2)만큼이 필요하다.

따라서 dp[i][j] = 최대 반지름이 i인 원을 빨강 페인트 j통을 사용해서 색칠하는 경우의 수로 두었고 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i](가장 바깥 원을 어떤 색으로 칠할지를 나누어서) 가 나오게 된다.

 

이 DP를 전처리 해 두고 테스트 케이스에서 가능한 원의 크기마다 빨강 페인트의 사용 가능 범위인 max(0, 총 페인트량 - b)(파랑 페인트를 최대로 사용) 부터 a + 1(빨강 페인트를 최대로 사용) 이 나오니 이를 누적합으로 만들어서 해결하였다.

 

1시 57분 32초 제출, 64점

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long int dp[450][50002];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T, tmp = 0;
	dp[0][1] = 1;
	for (int i = 1; i < 450; i++){
		tmp += i;
		for (int j = 0; j + i <= 50001; j++){
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % 1000000007;
			dp[i][i + j] = (dp[i][i + j] + dp[i - 1][j]) % 1000000007;
		}
	}
	for (int i = 1; i < 450; i++){
		for (int j = 1; j <= 50001; j++){
			dp[i][j] = (dp[i][j - 1] + dp[i][j]) % 1000000007;
		}
	}
	cin >> T;
	while (T--){
		long long int a, b, ans = 0;
		tmp = 0;
		cin >> a >> b;
		for (int i = 1; i < 450; i++){
			tmp += i;
			if (tmp > a + b) break;
			ans = (ans + 1000000007 + dp[i][a + 1] - dp[i][max((long long int)0, tmp - b)]) % 1000000007;
		}
		cout << ans << '\n';
	}
	
	return 0;
}

 

1부터 450까지의 합이 100000을 넘어 괜찮을 것 같았는데 범위가 큰 서브테스크에서 오답이 나와서 범위를 450에서 500으로 늘려주자 해결되었다.

 

 

2시 5분 18초 제출, 100점

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long int dp[500][50002];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T, tmp;
	dp[0][1] = 1;
	for (int i = 1; i < 500; i++){
		for (int j = 1; j + i <= 50001; j++){
			dp[i][i + j] = (dp[i][i + j] + dp[i - 1][j]) % 1000000007;
		}
		for (int j = 1; j <= 50001; j++){
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % 1000000007;
		}
	}
	for (int i = 1; i < 500; i++){
		for (int j = 1; j <= 50001; j++){
			dp[i][j] = (dp[i][j - 1] + dp[i][j]) % 1000000007;
		}
	}
	cin >> T;
	while (T--){
		long long int a, b, ans = 0;
		tmp = 0;
		cin >> a >> b;
		for (int i = 1; i < 500; i++){
			tmp += i;
			if (tmp > a + b) break;
			ans = (ans + 1000000007 + dp[i][a + 1] - dp[i][max((long long int)0, tmp - b)]) % 1000000007;
		}
		cout << ans << '\n';
	}
	
	return 0;
}