dgddgd   2년 전

- 문제를 나누어서 풀어봅시다.

만약 이분 그래프 문제인 것을 알았지만 이것을 검증하는 것을 잘 모르겠다면 : 

bfs / dfs로 검증 가능합니다. 시간복잡도는 최적화된 경우 O(N) 만에 가능합니다. 

이와 관련된 가장 대표적인 문제는 

https://www.acmicpc.net/proble... #1707 입니다. 만약 해당 문제를 풀었다면

https://www.acmicpc.net/proble... #17209 도 확인해보면 감이 옵니다.


이분 그래프 문제인 것을 알고 검증까지 했다면 냅색에서 막히는 것입니다 : 

그리디로 풀리지 않습니다. 8, 7, 5, 5, 5의 경우 그리디로 풀면 +8-7-5+5-5로 4이지만 최적의 해는 +8+7-5-5-5입니다.

(아랫 분의 말이 맞았습니다... 쉽다고 생각한 부분에서 발목 잡힐줄은)

dp가 최적인지는 모르겠지만 이 문제의 경우 시간 안에 풀 수 있습니다.


-

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