KOI 2016 중등부 해설

1. 방배정

아이디어는 초등부 문제와 같다.

2019/10/10 - [koi해설] - KOI 2016 초등부 해설

2. 주유소

처음에는 lis문제인줄 알았는데 10줄정도로 짤 수 있는 쉬운 문제였다.

주유하는 곳의 가격이 떨어지는 곳에서 계속 충전해주면 된다.(가격이 떨어지면 무조건 선택)

 

3. 트리

disjoint set 문제이다. 하지만 쿼리를 위에서부터 처리하면 당연히 시간초과가 나기 때문에 아래서부터 반대로 처리해야 한다.(즉, 모두 분리되어 있는 서로소 집합에서 하나씩 간선을 추가한다) 그 과정에서 부모 노드의 정보를 압축하는 과정도 처리해줘야 한다.

 

4. 레이저 센서

아직...