[백준/BOJ] 백준 2923번 : 숫자 게임

www.acmicpc.net/problem/2923

2923번: 숫자 게임

temp_A의 작은수 + temp_B의 큰수 < temp_A의 작은수가 아닌 다른 수 + temp_B의 큰수 이므로 이 조합(temp_A의 작은수 + temp_B의 큰수)은 temp_B에서 큰 수를 골랐을때 어떠한 수 보다 작은 조합이 된다 그러므로 이러한 조합들 중 가장 큰 값을 구하는 방법으로 문제를 해결한다 

 

코드

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

int n;
vector<int> A(101, 0);
vector<int> B(101, 0);

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int a, b;

		cin >> a >> b;

		A[a]++;
		B[b]++;

		vector<int> temp_A(A);
		vector<int> temp_B(B);

		int left = 1;
		int right = 100;

		int temp_max = -1;

		while (1)
		{
			//체크 되어 있는곳까지 이동
			while (left <= 100 && temp_A[left] == 0)
				left++;

			//체크 되어 있는곳까지 이동
			while (right >= 1 && temp_B[right] == 0)
				right--;

			if (left > 100 || right < 1)
				break;

			//고를 수 있는 조합중 temp_A의 작은수와 temp_B의 큰수의 합
			//temp_A의 작은수 + temp_B의 큰수 < temp_A의 작은수가 아닌 다른 수 + temp_B의 큰수
			//이 조합(temp_A의 작은수 + temp_B의 큰수)은 temp_B에서 큰 수를 골랐을때 어떠한 수 보다 작은 조합이 된다
			//그러므로 이러한 조합들 중 가장 큰 값을 구하는 방법으로 문제를 해결한다 
			temp_max = max(temp_max, left + right);

			//사용한것 개수 마이너스 -> 시간 오래걸림
			//temp_A[left]--; 
			//temp_B[right]--;

			//확인한 조합은 제외
			int min_cnt = min(temp_A[left], temp_B[right]);
			temp_A[left] -= min_cnt;
			temp_B[right] -= min_cnt;
		}

		cout << temp_max << "\n";
	}


	return 0;
}