글 읽기 - dp이외의 방법으로 풀었는데 질문 드립니다.

dladydwo123 5년 전 0

남자성격과 여자 성격을 오름차순으로 정렬한 후, 동일한 인덱스에 해당하는 남자성격과 여자성격의 차이를 info에 담고, table에는 어떤 남자와의 성격차이 값인지를 담았습니다. 이후에는 탐욕법을 적용했는데, 논리는 다음과 같습니다.

1. 수가 부족한 성별을 정합니다.

2. 짝지어진 커플(info)중 뒤부터, 커플이 아닌 사람과의 성격차이를 구하여, 제일 작은 값을 찾습니다.

3. 이를 0번 인덱스에 도달할 때 까지 계속합니다.

이해를 돕고자 그림으로 나타내 보면

<초기>

1번 남자 2번 남자 3번 남자 4번 남자 5번 남자.

1번 여자 2번 여자 3번 여자

<진행 중>

1번 남자 2번 남자 3번 남자 4번 남자 5번 남자

1번 여지 2번 여자 3번 여자 //3번 여자가 5번 남자와 커플이 되었을 때 성격차이 값이 줄어들었음.

<진행 중 2>

1번 남자 2번 남자 3번 남자 4번 남자 5번 남자.

1번 여자 2번 여자 3번 여자 //2번 여자가 3번 남자와 커플이 되었을 때 성격차이 값이 줄어들었음.

이런 식으로 작성했습니다. 해당 방식으로 작성 후 제출했는데 틀렸습니다가 나옵니다. 혹시 제가 세운 논리에 논리적 헛점이 있는지 알고싶습니다.

도와주시길 부탁그립니다. (_ _).

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<set>
#include<iostream>
#define ll long long
#define ull unsigned long long
using namespace std;

const int MAX = 2100000000;

int min(int a, int b) {
	if (a < b) return a;
	return b;
}

int max(int a, int b) {
	if (a > b) return a;
	return b;
}

int N,M;
int m_info[1001];
int w_info[1001];
int cnt;

int main() {
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		scanf("%d", &m_info[i]);
	}
	sort(m_info, m_info + N); //오름차순 배열
	for (int i = 0; i < M; i++) {
		scanf("%d", &w_info[i]);
	}
	sort(w_info, w_info + M); //오름차순 배열

	ll total = 0;
	int info[100001] = { 0, };
	int table[100001] = { 0, };
	if (N > M) { //남자가 많음으로 여자가 기준.
		for (int i = 0; i < M; i++) {
			info[i] = abs(w_info[i] - m_info[i]);
			table[i] = i;
		}
		table[M] = N;
		//뒤에서 부터 움직인다.
		for (int i = M - 1; i >= 0; i--) {
			for (int j = table[i]+1; j < table[i + 1]; j++) {
				if (info[i] > abs(w_info[i] - m_info[j])) {
					info[i] = abs(w_info[i] - m_info[j]);
					table[i] = j;
				}
				else
					break;
			}
		}
		for (int i = 0; i < M; i++) {
			total += (ll)info[i];
		}
	}
	else { //여자가 많음으로 남자가 기준,
		for (int i = 0; i < N; i++) {
			info[i] = abs(w_info[i] - m_info[i]);
			table[i] = i;
		}
		table[N] = M;
		//뒤에서 부터 움직인다.
		for (int i = N - 1; i >= 0; i--) {
			for (int j = table[i]+1; j < table[i + 1]; j++) {
				if (info[i] > abs(m_info[i] - w_info[j])) {
					info[i] = abs(m_info[i] - w_info[j]);
					table[i] = j;
				}
				else
					break;
			}
		}
		for (int i = 0; i < N; i++) {
			total += (ll)info[i];
		}
	}

	printf("%lld", total);
	return 0;
}

djm03178 5년 전 1

로직을 정확히 이해한 것인진 모르겠지만, 다음과 같은 입력에서

4 3

1 2 4 4

3 3 3

이 코드는 4를 출력하는데, 정답은 3입니다. 이 코드에서는 아마도 앞의 셋끼리 짝을 지을 것 같은데, 세번째 여자는 세번째 남자와 짝을 짓나 네번째 남자와 짝을 짓나 그 자체로는 차이가 없지만, 그 때의 선택으로 인해 두번째와 첫번째 여자가 할 수 있는 선택에 제한을 두게 됩니다.

좀 더 극단적으로는 다음과 같은 예를 들 수 있습니다.

3 2

1 99 100

98 99

dladydwo123 5년 전 0

지적해 주신 사항은 차이값을 비교할 때, > 인 부분을 >=으로 수정하여 해결했습니다.

혹시 뒷 사람이 손해를 보더라도, 이전에 결정한 커플보다 성격차이가 큰 사람과 커플을 만들 경우, 전체적인 성격차이 합이 낮아지는 경우도 있습니까? 제 생각으론 오름차순으로 정렬해 놓았기 때문에, 탐욕법이 적용될 수 있다고 봤는데...

djm03178 5년 전 0

55번째 줄과 76번째 줄을 >=로 바꾸셨다는 의미지요? 여전히 같은 문제가 있습니다.

지금 보는 한 사람에 대한 결정 때문에 나머지 사람들이 강제적으로 제한된 범위에서만 짝을 맺을 수 있다면, 손해가 나는 경우가 있을 수 있죠.

2
99 102
100

dladydwo123 5년 전 0

정말 감사합니다. 궁금증이 풀렸습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dp이외의 방법으로 풀었는데 질문 드립니다.

dladydwo123 5년 전 0

djm03178 5년 전 1

dladydwo123 5년 전 0

djm03178 5년 전 0

dladydwo123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말