본문 바로가기

알고리즘/Baekjoon

이분 매칭. [9576]

[1. 문제 설명]

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


[2. 풀이 접근]

이분 매칭으로 접근하는 방법

  • 사람에서 책 으로 연결리스트를 구축
    # 이 과정에서 책 번호의 범위에 대한 조건이 반영 된다.
  • 이 상태에서 이분 매칭을 구한다.

 

탐욕법으로 접근하는 방법

  • 책 번호 범위가 가장 작은 사람 부터 책을 할당한다.
  • 정당성 입증 필요..

 

이분 매칭에서 탐욕법을 적용하는 것이 아니라

이분 매칭 풀이법과 탐욕법으로 해결하는 방법이 있다고 보면 되고,

이분 매칭은 탐색 과정 의미를 알 필요가 있다.


[3. 코드]

이분 매칭으로 구하는 방법은 생략.

 

 

'알고리즘 > Baekjoon' 카테고리의 다른 글

완전 탐색. [15686]  (0) 2023.08.18
동적계획법. [9461]  (0) 2023.08.18
이분매칭. [2188], [11375]  (0) 2023.05.27
동적계획법. [11727]  (0) 2023.05.24
네트워크 유량. [11405]  (1) 2023.05.17