[백준/C++] 5911 선물

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

오랜만에 구현력도 기를겸 실버 문제를 살살 건드리고 있습니다. 해당 문제는 한번 헷갈려서 정리를 해보겠습니다.

일단 기본 입력값들의 범위가 주어집니다.

입력되는 N의 범위는 (1 <= N <= 1000) 명이기 때문에 3중 포문까지는 불가능할 것입니다. 1억당 1초로 계산하기 때문에 그래서 최대 이중 포문으로 문제를 해결해야 할 것입니다.

여기 문제에서는 약간의 훼이크를 주는데 돈의 범위가 B(1 <= B <= 1,000,000,000) 까지 즉, 10억 까지기 때문에 int 범위 내에서 해결이 가능합니다. 똑같이 선물의 가격, 배송비도 B의 범위와 같기 때문에 int 범위내에서 해결이 가능합니다.

일단 입력값들의 범위는 부담이 되지 않으니, 최대 이중 포문에서 해결할 생각을 해야합니다.

그리고, 이 문제의 중요한 점은 N개의 선물의 가격과 배송비가 주어지는데 무작위로 주어진다는 것입니다. 우리는 최대의 선물 개수를 구해야하기 때문에, 무작위로 모든 값을 살펴보기엔 부담이 생기기 마련입니다.모든 조합을 살펴봐야 하기 때문이죠.. 그래서 첫번째로 생각한 것은 정렬을 하자는 것입니다.

정렬의 기준은 어떻게 하냐면? 일단 최대의 선물 개수를 골라야 하기 때문에 선물 값 + 배달 비를 합친게 제일 작은 것 그리고 이 두개를 합친 값이 같다면? 선물의 값을 1/2를 시킬 수 있기 때문에 선물의 값이 작은 것을 먼저 구매를 하는 것이죠.

여기서 제가 잠깐 헷갈렸던것은? 마지막 선물을 구매했을때, 어차피 얘가 마지노선이고 얘를 1/2 가격으로 산다면? 충분히 뒤에까지 살펴보지 않아도 최대 값을 구할 수 있을 것이다! 라고 생각을 했다는 것입니다. 심지어 nlogn + n의 크기로 해결도 가능하고요.

이런 방식으로 문제를 해결했는데, 정확히 83%에서 더이상 올라가지 않았습니다. 그렇다면 어떤것이 문제일까? 고민을 했다 이거죠.

문제는 정렬 방식과 선물의 값을 1/2를 줄일 수 있다는 것을 간과했다는 것입니다. 그리고 정렬 방식 때문에 결국 선물 값과 배송값의 합이 같다면? 선물의 값이 큰게 뒤로 정렬이 된다는 것입니다.

그리하여, 나의 해결방법의 문제는 N = 2, B = 1, (선물 가격 = 0, 배송 가격 = 2) , (선물 가격  = 2, 배송 가격 = 0) 인 반례가 존재한다는 것입니다. 이건 자동으로 (선물 가격 = 2, 배송가격 = 0)이 잡히지 않고 재산이 1이기 때문에 깎이지 않고, 선물을 구매할 수 없다는 결론이 나오게 됩니다.

그래서, 이걸 어떻게 해결할 수 있을까? 생각을 했습니다. 그렇다면 먼저 선물 가격이 할인 된것을 먼저 고르고 나머지를 고른다면 어떻게 될까? 해결할 수 있지 않을까라는 생각을 했습니다.

그래서 정렬을 하고 이중 포문으로 해결한다면? nlogn + (n * n) 해서 문제를 해결한다면? 충분히 해결이 가능할 것 입니다.

그래서 아까처럼 말했던거 처럼, 첫번째 포문에서는 선물 가격이 1/2가 되어서 구매를 할 수 있다면? 그 값을 제외하고, 정렬된 배열을 두번째 포문에서 순회하면서 최대 선물 개수를 구하는 것입니다.

코드는 아래와 같습니다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n,m,ip,dp;
vector<pair<int,int> > v;

void init() {
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		cin >> ip >> dp;
		v.push_back({ip,dp});
	}
	
}

bool comp(pair<int,int>& a, pair<int,int>& b){
	
	if(a.first + a.second == b.first + b.second){
		return a.first < b.first;
	}
	return a.first + a.second < b.first + b.second;
	
}

int main() {
	
	init();
	sort(v.begin(), v.end(), comp);
	
	int cnt = 0, chk = 1;
	
	for(int i = 0; i < n; i++){
		
		int a = v[i].first;
		int b = v[i].second;
		
		if(m - (a + b) < 0){
			if(m - (a / 2 + b) >= 0){
				m -= (a/2) + b;
				cnt++;
			} else{
				chk = false;
			}
		} else{
			m -= (a + b);
			cnt++;
		}
		
		if(!chk) break;
	}
	
	cout << cnt;
	
	return 0;
} // 실패한 코드 ㅋ

 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n,m,ip,dp;
vector<pair<int,int> > v;

void init() {
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		cin >> ip >> dp;
		v.push_back({ip,dp});
	}
	
}

bool comp(pair<int,int>& a, pair<int,int>& b){
	
	if(a.first + a.second == b.first + b.second){
		return a.first < b.first;
	}
	return a.first + a.second < b.first + b.second;
	
}

int main() {
	
	init();
	sort(v.begin(), v.end(), comp);
	
	int answer = 0, cnt = 0, chk = 1;
	
	for(int i = 0; i < n; i++){
		
		int reserved = m;
		
		int a = v[i].first;
		int b = v[i].second;
		
		if(a / 2 + b <= reserved) {
			cnt = 1;
			reserved -= (a / 2) + b;
		} else {
			cnt = 0;	
		}
		
		for(int j = 0; j < n; j++){
			
			if(i == j) continue;
			
			int _a = v[j].first;
			int _b = v[j].second;
			
			if(_a + _b <= reserved){
				cnt++;
				reserved -= (_a + _b);
			} else{
				break;
			}
			
		}
		
		answer = max(answer, cnt);
		
	}
	
	cout << answer;
	
	return 0;
} // 성공한 코드 ㅎ