[백준/BOJ] 백준 22348번 : 헬기 착륙장

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

22348번: 헬기 착륙장

 

사용한 파랑 페인트 수는, 어떠한 반지름의 원을 그린 상황에서 사용한 빨강 페인트양을 알면, 사용한 파랑 페인트양을 알 수 있다는 것을 이용했는데, 예를 들어 파랑 페인트 수는 n번째 원을 그린 상황에서 "n*(n+1)/2 - 사용한 빨강 페인트" 만큼 사용했다는 것을 알 수 있다.

 

이를 이용해 cache에 cache[반지름 크기][사용한 빨강 페인트] = "해당 반지름 크기의 헬기 착륙장을 정확히 사용한 빨강 페인트 만큼 사용해서 만드는 경우의 수"를 구하고, cache를 반지름을 기준으로 사용 가능한 빨강 페인트에 대한 누적합을 구해서 해당 반지름 크기의 헬기 착륙장을 만드는데 최대 A를 [0~A]개를 사용해서 만드는 경우의 수를 psum[반지름][A]에 저장해 놓는다.

 

cache는 bottom up 방식으로 채우며, 이전에서 빨강 페인트를 사용해서 r 반지름의 원으로 온 경우와 이전에서 파랑 페인트를 사용해서 r 반지름의 원으로 온 경우 두가지를 고려해서 값을 채웠다.

 

psum을 만들어 놓은 이유는, 테스트 케이스에서 사용한 빨강 페인트 양이 a이하, 사용한 파랑 페인트 양이 b이하인 모든 경우의 수를 빠르게 구하기 위해서 이다.

 

또한 위 연산 중 "result = (result + (psum[i][red_right] - psum[i][red_left - 1]) + 1000000007) % 1000000007"을 수행할 때, "%1000000007"를 수행하기 전에  "+1000000007"을 수행하는 것을 볼 수 있는데, 이는 psum에 들어가 있는 값 자체가 "%1000000007" 연산을 한 값이 들어가므로, 실제 값과 달리 psum에 들어가 있는 값 자체는 psum[i][red_left - 1]이 psum[i][red_right]보다 큰 경우가 있을 수 있기 때문이다. 즉, psum[i][red_right] - psum[i][red_left - 1]가 음수가 나올 수 있기 때문에 이러한 상황을 방지하기 위해 "+1000000007"을 수행하는 것이다. 

 

코드

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

int t;

//특정 원을 그린 상황에서 사용한 빨강 페인트(파랑 페인트)양을 알면, 사용한 파랑 페인트(빨강 페인트)양을 알 수 있다.
//n번째 원을 그린 상황에서, 사용한 빨강 페인트 양이 A일때, 사용한 파랑 페인트 양을 B라고 하면, n번째 원까지 그리는데 사용한 전체 페인트의 양은 n*(n+1)/2 이므로
//B = n*(n+1)/2 - A

//빨강 페인트 50,000통 파랑 페인트 50,000통을 가지고 있는 상황이라고 할때
//색깔 구분 없이 총 100,000통을 가지고 있는 상황이라도 그릴 수 있는 헬기 착륙장의 크기는 500 보다 작다.
long long cache[505][50005]; //[반지름 크기][사용한 빨강 페인트] = 해당 반지름 크기의 헬기 착륙장을 만드는 경우의 수
long long psum[505][50005]; //[반지름 크기][빨강 페인트 수] = 해당 반지름 크기의 헬기 착륙장을 만드는데 빨강 페인트를 [0~빨강 페인트 수]개를 사용해서 만드는 경우의 수

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

	cache[0][0] = 1;
	for (int i = 1; i <= 500; i++) {
		for (int j = 0; j <= 50000; j++) {
			int r = i;
			int used_red = j;
			int used_blue = (r)*(r + 1) / 2 - used_red;

			if (used_blue < 0) { //지금까지 사용한 파랑 페인트의 양이 음수가될때
				continue;
			}

			//이전에서 빨강 페인트를 사용해서 r 반지름의 원으로 온 경우
			if (used_red - r >= 0) {
				cache[r][used_red] = (cache[r][used_red] + cache[r - 1][used_red - r]) % 1000000007;
			}

			//이전에서 파랑 페인트를 사용해서 r 반지름의 원으로 온 경우
			cache[r][used_red] = (cache[r][used_red] + cache[r - 1][used_red]) % 1000000007;
		}
	}

	//아래에서 사용한 빨강 페인트 양이 a이하, 사용한 파랑 페인트 양이 b이하인 모든 경우의 수를 빠르게 구하기 위해 누적합을 구해 놓는다
	for (int i = 1; i <= 500; i++) {
		psum[i][0] = cache[i][0];
		for (int j = 1; j <= 50000; j++) {
			psum[i][j] = (psum[i][j - 1] + cache[i][j]) % 1000000007;
		}
	}

	cin >> t;

	for (int tc = 0; tc < t; tc++) {
		int a, b;
		cin >> a >> b;

		long long result = 0;

		//사용한 빨강 페인트 양이 a이하, 사용한 파랑 페인트 양이 b이하인 모든 경우의 수 구하기
		//즉 반지름을 r이라고 할때
		//r*(r+1)/2 - a(최대 사용 가능한 빨강 페인트 양)(=> 최소 사용 파랑 페인트 양) <= b(사용 가능한 파랑 페인트 양) 가 되어야 한다.
		//즉 빨강 페인트는 r*(r+1)/2 - b <= a 로 최소 r*(r+1)/2 - b 이상이 되어야 한다
		//즉 빨강 페인트를 사용 가능한 양은 a이하, r*(r+1)/2 - b 이상이 된다.
		for (int i = 1; i <= 500; i++) {
			int r = i;
			int red_left = r * (r + 1) / 2 - b; //빨강 페인트 사용 가능 양은 r*(r+1)/2 - b 이상
			int red_right = a; //빨강 페인트 사용 가능 양은 a 이하

			if (red_left > red_right) {
				continue;
			}

			if (red_left <= 0) {
				result = (result + (psum[i][red_right]) + 1000000007) % 1000000007;
			}

			else {
				//psum 자체도 "%1000000007" 연산을 한 값이 들어가므로
				//실제 값과 달리, psum에 들어가 있는 값 자체는 psum[i][red_left - 1]이 psum[i][red_right]보다 큰 경우가 있을 수 있어서
				//psum[i][red_right] - psum[i][red_left - 1] 가 음수가 나올 수 있다
				//예를 들어 위에 psum을 채울때 psum[i][red_left - 1]는 1000000000이 저장되고, 
				//psum[i][red_right]에는 1000000008이 들어가야 되는데, "%1000000007" 연산으로 인해 1이 저장되는 경우
				//즉 이러한 경우를 방지하기 위해 "+1000000007"을 꼭 해야 한다
				result = (result + (psum[i][red_right] - psum[i][red_left - 1]) + 1000000007) % 1000000007;
			}

		}

		cout << result << "\n";
	}


	return 0;
}