백준 22348 헬기 착륙장

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

22348번: 헬기 착륙장

 

풀이 

해당 문제에서 직관적으로 보이는 상태 DP를 만들면 이렇습니다.

DP[n번째 원까지 그린상황][사용한 빨간페인트][사용한 파란페인트]인 경우의 수

 

하지만 입력으로들어오는 a와 b는 최대 50000까지이고 그렇기 때문에 n은 대략 500까지정도 들어옵니다.

n x a x b = 500 x 50000 x 50000 = 1,250,000,000,000이므로 해당 배열을 만들면 메모리초과,

설사 만들어도 전부 탐색하면 시간초과가 나올 것입니다.

 

 

 

다행이 우리는 파란페인트의 양을 유도 할 수 있습니다.n번째 원까지 그렸다면 사용한 페인트수는 n x (n+1) / 2 이기 때문에

(파란 페인트 사용 횟수) = n x (n+1) / 2 - (빨간 페인트 사용 횟수)로 유도가 가능합니다.

 

 

파란 페인트를 상태 DP에서 지웠으니 사용할만한 크기의 상태 DP가 만들어졌습니다.

DP[n번째 원까지 그린상황][사용한 빨간페인트]인 경우의 수
//빨간페인트 사용횟수를 통해 파란페인트 사용횟수도 알 수 있다.

 

 n x a = 25,000,000 이므로 해당 방법으로 접근할만합니다.

DP[n+1][a+(n+1)] += DP[n][a]; //빨간페인트를 사용한 경우
DP[n+1][a] += DP[n][a]; //파란페인트를 사용한 경우

 

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

int DP[502][50001];
const int MOD = 1000000007;

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);

	int T;
	cin >> T;
	while (T--)
	{
		int red, blue;
		cin >> red >> blue;

		memset(DP, 0, sizeof(DP));

		int ans = 0;
		DP[0][0] = 1;
		for (int i = 0; i <= 500; i++)
			for (int j = 0; j <= red; j++)
			{         	
				//사용한 페인트수 
				int a = i*(i+1)/2;
				int b = a - j;
				int r = j;

				if (r + (i + 1) <= red)
					DP[i + 1][j + (i + 1)] = (DP[i + 1][j + (i + 1)] + DP[i][j]) % MOD;
				if (b + (i + 1) <= blue)
					DP[i + 1][j] = (DP[i + 1][j] + DP[i][j]) % MOD;
			}

		for (int i = 1; i <= 500; i++)
			for (int j = 0; j <= red; j++)
				ans = (ans + DP[i][j]) % MOD;

		cout << ans << endl;
	}
}

 

 

 

하지만 해당 방식으로는 90점 밖에 받을 수 없습니다!!

 

6번부터는 T가 10000까지 주어지기 때문에

T x n x a = 10000 x 500 x 50000 = 250,000,000,000으로 나오기 때문에 시간초과가 나올 것입니다.. ㅠㅠ

조금 더 시간을 줄이기 위한 아이디어가 필요합니다.

DP를 재사용하도록 생각을 해봅시다.

DP를 매번 만들 필요가 없을지도 모릅니다.

미리 DP값을 구해놓고 정답에 맞는 조건에 해당하는 값만 더해주면 됩니다.

 

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

int DP[502][50001];
const int MOD = 1000000007;

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);

	//여러 경우에 따라 나오는 상태DP값을 만들어놓는다.
	DP[0][0] = 1;
	for (int i = 0; i <= 500; i++)
		for (int j = 0; j <= 50000; j++)
		{
			if (j + (i + 1) <= 50000)
				DP[i + 1][j + (i + 1)] = (DP[i + 1][j + (i + 1)] + DP[i][j]) % MOD;
			DP[i + 1][j] = (DP[i + 1][j] + DP[i][j]) % MOD;
		}

	int T;
	cin >> T;
	while (T--)
	{
		int red, blue;
		cin >> red >> blue;

		int ans = 0;
		for (int i = 1; i <= 500; i++)
			for (int r = 0; r <= red; r++)
			{
				//사용한 페인트수 
				int a = i * (i + 1)/2;
				int b = a - r;

				//정답에 맞는 경우에만 더해준다.
				if (b <= blue && r <= red)
					ans = (ans + DP[i][r]) % MOD;
			}

		cout << ans << endl;
	}
}

 

 

 

DP를 미리 만들어 놓은 것을 사용하게 만들었지만 아직 90점짜리 코드입니다.

 

 

밑줄 그은 부분을 수정해서 다른 시점에서 보면..

b ≤ blue를 치환하면 a - r ≤ blue 이 되고

a - blue ≤ r로 수정이 가능합니다. 

a - blue 이상 red이하인 DP [i][r]을 모두 합하는 식으로 치환이 되었고 

해당 합을 구하는 방법은 누적합을 미리 전처리해놓는 걸로 쉽게 구할 수 있습니다.

전 처리해놓은 것으로 총 T x n = 10000 x 500 = 5000000으로 시간 안에 정답을 구할 수 있습니다. 

 

자세한 부분을 코드를 참고해주세요. (코드는 별로 안어려워요 ㅠ)

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

int DP[502][50001];
int S[502][50001];
const int MOD = 1000000007;

//s부터 e까지의 합을 구하는 함수
int Sum(int i, int s, int e)
{
	if (e < s)
		return 0;
	return (S[i][e] - (s > 0 ? S[i][s - 1] : 0) + MOD)%MOD;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);

	//여러 경우에 따라 나오는 상태DP값을 만들어놓는다.
	DP[0][0] = 1;
	for (int i = 0; i <= 500; i++)
		for (int j = 0; j <= 50000; j++)
		{
			if (j + (i + 1) <= 50000)
				DP[i + 1][j + (i + 1)] = (DP[i + 1][j + (i + 1)] + DP[i][j]) % MOD;
			DP[i + 1][j] = (DP[i + 1][j] + DP[i][j]) % MOD;
		}
       
    //누적합을 전처리하는 코드
	for (int i = 0; i <= 500; i++)
	{
		S[i][0] = DP[i][0];
		for (int j = 1; j <= 50000; j++)
			S[i][j] = (S[i][j - 1] + DP[i][j]) % MOD;
	}

	int T;
	cin >> T;
	while (T--)
	{
		int red, blue;
		cin >> red >> blue;

		int ans = 0;
		for (int i = 1; i <= 500; i++)
		{
			int a = i * (i + 1) / 2;
            
            //a-blue부터 red까지 합을 더해준다.
			ans = (ans + Sum(i, a - blue, red)) % MOD;
		}

		cout << ans << endl;
	}
}