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

제 271회 웰노운컵이라고 풀이는 검색하면 나오는 그리디 문제 있는데

검색해서 나오는 거랑 전혀 다른 세그 쓰는 그리디 풀이를 짰는데

오후 종일 고민해도 증명을 못 함

http://boj.kr/7b9aa60c7ff347b5b0102d70c4c66784


A 배열을 B 기준으로 정렬을 해놓은 상태에서

A 배열의 값을 값이 큰 것부터 쓸지 안 쓸지 정하는데

레이지 세그를 이용해서 써도 유효한 매칭을 만들 수 있으면 쓰고 없으면 안 쓰는 방식으로 짰음


레이지 세그가 체크하는 조건을 만족하면 유효한 매칭을 만들 수 있음은 증명했는데

증명이 안 되는 건 저 방식이 왜 최적인지를 못 하겠음...