[BOJ 2923] 숫자 게임

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

2923번: 숫자 게임

 

- 문제 요약

 

창영이와 현우는 여러 라운드로 이루어진 게임을 하고 있다.

매 라운드가 시작할 때, 현우는 창영이에게 100보다 작은 두 숫자 A와 B를 말해준다.

그러고 난 뒤, 창영이는 다음과 같은 문제를 풀어야 한다.

지금까지 현우가 말한 모든 A와 모든 B를 짝짓는다.

이때, 각 쌍의 합 중에서 가장 큰 값을 작게 만들어라.

즉, 현재 라운드가 N 라운드이라고 하면, 현우가 창영이에게 말한 숫자는 a1, a2,..., an과 b1, b2,..., bn이라고 할 수 있다. 이때, 각 숫자를 한 번씩 사용하여 (ai, bj) 쌍을 n개 만들 수 있다.

이렇게 쌍을 모두 만들었을 때, ai+bj의 합 중 가장 큰 값을 가능한 작게 만들어야 한다.

 

 

- 알고리즘 정리

 

A에서 가장 큰 값과 B에서 가장 작은 값을 더하는 것은 가장 큰 값이 아니라고 가정했습니다.

현우가 말한 숫자 는 A와 B가 입력으로 들어올 때, 현재까지 들어온 A 중 가장 큰 값과 B를 더하는 식으로 그리디 하게 문제를 해결했습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 101
int n,arr[MAX],brr[MAX],result,mx,mn;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;	
		vector<int>v1(MAX),v2(MAX);
		arr[a]++;
		brr[b]++;
		for(int j=0;j<MAX;j++){
			v1[j]=arr[j];
			v2[j]=brr[j];
		}
		result=0,mx=100,mn=1;
		while(mx>=1&&mn<MAX){
			while(mx>=1&&v1[mx]==0){
				mx--;
			}
			while(mn<MAX&&v2[mn]==0){
				mn++;
			}
			if(mx==0||mn==MAX){
				break;
			}
			result=max(result,mx+mn);
			if(v1[mx]>v2[mn]){
                v1[mx]-=v2[mn];
                v2[mn]=0;
			}
			else{
				v2[mn]-=v1[mx];
				v1[mx]=0;
			}
		}
		cout<<result<<'\n';
	}
}

코드 제출 결과

오늘의 한 줄 : 내다버린 10분 (변수 이름은 잘 알아볼 수 있도록 지어봅시다...^^)