글 읽기 - 그리디 풀이 질문

tjdgnsqn3 1년 전 0

1. min(N, M)개의 커플을 만든다.

2. 커플의 성격차이는 최소가 되어야 한다.

를 이용해서 그리디 하게 풀었는데요.

우선 오름차순으로 정렬하고 upper bound를 쉽게 활용하기 위해 multiset을 이용했습니다.

A라는 multiset이 항상 커플이 많은 경우라면

B라는 multiset을 iterate하면서 A에 적절히 매칭해주면 답이 나오는 것으로 생각했습니다.

1. b를 통해 A에서 upper_bound를 구한다

2. upper_bound보다 previous element의 차이가 더 작거나 같으면 previous element와 매칭해준다.

3. 아니면 그냥 쓴다.

를 이용했는데 오류가 있을까요?

B와 A는 증가하는 수열이므로 위 1~3과정으로 진행하는 것이 그리디하다고 생각했습니다.

#include <bits/stdc++.h>

void solve(){
  int N, M; std::cin >> N >> M;

  std::multiset<int> A;
  std::multiset<int> B;
  for (int i = 0; i < N; i++) {
    int a; std::cin >> a;
    A.insert(a);
  }
  for (int i = 0; i < M; i++) {
    int b; std::cin >> b;
    B.insert(b);
  }

  long long result = 0;
  if (A.size() < B.size()) std::swap(A, B);
  assert(A.size() >= B.size());
  for (auto b : B) {
    auto it = A.upper_bound(b);
    if (A.end() == it) --it;
    if (it != A.begin() && std::abs(*it - b) >= std::abs(*std::prev(it) - b)) --it;
    result += std::abs(*it - b);
    A.erase(it);
  }
  std::cout << result;
}

int main(){
  std::cin.tie(0)->sync_with_stdio(false);
  solve();
  return 0;
}

pjshwa 1년 전 1

3 3

3 9 2

8 10 10

가 반례입니다. 정답: 14

tjdgnsqn3 1년 전 0

@pjshwa

감사합니다.

이후에 선택될 b가 이미 사라진 element를 선택하는게 최적인 경우가 있군요.

그러면 이후 선택될 엘리먼트의 최적 상태를 구해야하는데, 항상 구할 수 없으니 dp로 풀어야겠네요

tjdgnsqn3 1년 전 0

문제에 그리디 태그가 있던데, 혹시 그리디로 푸는것도 가능할까요??

ksc919 1년 전 0

도움되는 댓글이 아니라 죄송합니다..

저도 이제 기초그리디 문제들을 좀 접하고 있는데...

이 문제를 어떻게 그리디로 풀 수 있나요?

저도 너무 궁금합니다;;

tkdgus5828 1달 전 0

저도 처음에는 그리디 알고리즘으로만 접근하다가 틀려서,

혼자 공부하면서 저 나름대로 이해한걸 공유드립니다.

제 생각에 이 문제는,

1. 그리디만 가지고 풀 수 없는 문제

2. 그리디를 적용한 DP를 이용하는 문제

라고 생각합니다.

그리디만 적용하면 틀리는 이유

일단 바로 반례를 보면,

4 6

30 40 80 90

1 39 50 70 89 200

위 예시의 정답은 30입니다.

(30-39 / 40-50 / 80-70 / 90-89)

여기서 그리디 알고리즘만 적용한다면 오답이 나옵니다.

(최적해: i번째 남자는 가장 성격 차이가 적은 사람을 선택한다)

오름차순으로 선택하면

30-39 / 40-50 / 80-89 (x) / 90-70 (x) = 48

내림차순으로 선택하면

90-89 / 80-70 / 40-39 (x) / 30-50 (x) = 32

최적해만 가지고는 최솟값이 나올 수 없습니다.

결국 모든 케이스를 탐색 해봐야 합니다.

그리디를 적용한 DP

결국 최적화를 위해 DP를 사용하는데 여기서도 규칙이 존재합니다.

(두 배열이 정렬되었다 가정 && 여자의 수가 남자의 수보다 많다 가정)

(k = 남자 번호, s[k] = 남자가 선택한 여자 번호)

' i < j 라면, s[i] < s[j] 여야 한다 '

최솟값이 나오도록 고르려면, 매칭 됐을 때 남자들의 선택이 교차되면 안됩니다.

(위의 그리디의 반례 케이스에서 그리디만 적용하면 교차되게 선택을 해서 오답이 나왔습니다)

이 규칙을 가지고 DP를 이용해 문제를 풀어야 합니다.

이 규칙을 적용했을 떄의 문제는

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

위 사이트의 문제의 유형과 거의 비슷해 집니다.

(위 사이트의 문제도 DP를 이용해 푸는 문제입니다)

결국 이 문제는 그리디를 적용한 DP를 이용해야 풀 수 있는 문제라고 생각합니다.

그래서 알고리즘 분류에 그리디와 DP가 같이 나왔다고 생각합니다.

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

문제

문제

출처

ICPC

그리디 풀이 질문

tjdgnsqn3 1년 전 0

pjshwa 1년 전 1

tjdgnsqn3 1년 전 0

tjdgnsqn3 1년 전 0

ksc919 1년 전 0

tkdgus5828 1달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말