AT2645 [ARC076D] 최소 의자 추가 문제
해결 방법 1
보조정리: 이분 그래프의 두 부분집합을 각각 X, Y(|X| ≤ |Y|)라고 할 때, 완벽한 매칭이 존재할 필요충분조건은 ∀S ⊆ X, f(S) ≥ |S| (여기서 f(S)는 S와 연결된 점들의 집합)이다. (즉, 홀의 정리)
문제에서 요구하는 것은 기본적으로 완벽한 매칭을 구성하기 위해 최소 몇 개의 의자를 추가해야 하는지를 묻고 있습니다.
따라서 모든 사람이 의자를 선택할 ...
7월 31일 18:34에 게시됨
로구 P2672 영업사원 문제 해결 (탐욕 알고리즘, 시뮬레이션)
해결 접근법
첫 번째 방법:
i번 가게를 선택하는 경우, 명백하게 a 값이 가장 큰 i-1개 가게는 반드시 선택해야 합니다. 따라서 마지막 가게 선택 방식만 고려하면 됩니다.
a 값이 i번째로 큰 가게를 선택하는 방법과, 남은 가게 중 s 값이 가장 큰 가게를 선택하는 방법 중에서 선택해야 합니다.
각 가게의 정보(s와 a)를 구조체에 저장한 후, a 값을 기준으로 내림차순으 ...
7월 8일 19:16에 게시됨