[백준/c++] 14042 - Tandem Bicycle

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

14042번: Tandem Bicycle

---

1) 풀이

각각 n명의 Dmojistan의 시민과 Pegland의 시민을 2인승 자전거에 한명씩 태우는데, 각 시민 개인의 자전거 속도를 a와 b라고 할 때 a와 b가 탄 2인승 자전거의 속도는 max(a,b)이다. (blockdmask.tistory.com/366 max() 함수에 대한 참고자료)

그리고 각 자전거의 속도를 더한 값을 속도의 총합이라고 할때 문제에서는 속도의 총합에 대한 질문이 두개 주어진다.

 

- 질문 1: 가능한 모든 경우 중, 가장 작은 속도의 총합은 얼마인가?

- 질문 2: 가능한 모든 경우 중, 가장 큰 속도의 총합 얼마인가?

 

우선, Dmojistan의 시민과 Pegland의 시민 각각의 자전거 속도를 저장해둘 벡터 두개를 준비한다.

그리고 주어지는 속도를 저장한 뒤, 각 벡터를 오름차순으로 정렬해준다.

 

질문 1에 대한 답을 구하기 위해서는 각각의 벡터에서 같은 인덱스끼리 max 함수에 집어넣어 비교를 하면 가장 작은 속도의 총합을 구할 수 있다.

 

질문 2에 대한 답은, 큰 숫자를 최대한 많이 속도의 총합에 더해주면 된다. 그말은, Dmojistan의 시민과 Pegland의 시민이 저장돼있는 벡터 두개를 서로 정 반대편 인덱스를 max에 넣어주면 큰 숫자를 많이 넣을 수 있다.

 

예를 들면, Dmojistan시민 벡터의 0번째 인덱스는 시민들의 속도 중 제일 작은 값일테고,

Pegland의 시민 벡터의 맨 마지막 인덱스는 그 시민들의 속도 중 가장 큰 값일 거다.

이거 두개를 max()함수에 집어넣으면 당연히 큰 속도가 반환될 거고

Dmojistan 벡터 인덱스를 1번째로, Pegland 벡터 인덱스를 맨마지막에서 바로 앞으로 옮겨서 max()함수에

집어넣고, 또 Dmojistan 벡터 인덱스는 뒤쪽으로 Pegland 벡터 인덱스는 앞쪽으로 옮겨가며 이 과정을 반복하면

결국 마지막엔 Dmojistan 벡터에서 가장 큰 값도 속도의 총합에 더해지는 등 최대한 큰 값들을 속도의 총합에 많이 더할 수 있게 된다.  

이렇게 설명해놓으니 이해가 잘 안 갈 수도 있는데, 자세한 것은 소스코드를 참조해주면 좋겠다! 

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
int q, n;
vector<int>d; //Dmojistan의 시민들
vector<int>p; //Pegland의 시민들
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> q >> n;
	int tmp;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		d.push_back(tmp);
	}
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		p.push_back(tmp);
	}
	sort(d.begin(), d.end());
	sort(p.begin(), p.end());
	int sum = 0;
	if (q == 1) { //질문1번에 대한 반복문
		for (int i = 0; i < n; i++) {
			sum += max(d[i], p[i]); //각 벡터에서 같은 인덱스끼리 비교
		}
		cout << sum << '\n';
	}
	else {
		for (int i = 0; i < n; i++) {
			sum += max(d[i], p[n - 1 - i]); //각 벡터에서 반대편 인덱스 비교
		}
		cout << sum << '\n';
	}
}

3) 참고자료

blockdmask.tistory.com/366