최근 푼 어려운 문제들 간단 요약

까먹기 전에 작성한다...
풀이를 안 보고 푼 문제가 거의 없다 ㅋㅋ.
IOI는 진짜 너무 좋은 셋이다.

1. Antennas

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

이 문제는 연습셋 도중에 풀이가 나왔었고, 정확히 정해랑 일치했는데, 시간이 없어서 셋 도중에 구현 못하기도 했고, 내 풀이에 자신이 없었다. 그냥 맞을거 같은데.. 까지는 나왔었는데, O(log n)번 이하로 작업이 이루어진다는 것을 증명하는 방법이 멋지니 꼭 알아두도록 하자. 증명 빼고는 나름? 웰노운 문제

 

 

2. 메기 농장
https://www.acmicpc.net/problem/25438

이 문제는 거의 접근 했고 풀이도 나왔는데, 핵심적인 관찰을 하지 못하면 구현이 매우 매우 더러워진다.
구간의 증감을 잘 살펴보면 segtree +dp 로 풀수 있다.
여러가지 관찰을 종합해서 잘 정리해야 멋지고 깔끔하게 구현할 수 있는 문제

 

3. .죄수들의 도전

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

어케 풀지?? 답 없다... 60점까지 긁는건 쉽고, 100점 풀이 떠올리는 것이 좀 어려운 것 같다...
정확히는 수열을 찾을 생각을 하는게 진짜 어려운 것 같다.

 

 

4. Split the attractions

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

일단 a<b<c로 고정된다는 것을 생각하기는 쉬운데, 거기서 진전이 없다.
그런데 풀이를 보면 이해하기는 쉽고, 이 걸 어떻게 떠올리지 라는 생각을 하면서 문제에 대한 경외감이 생긴다.
애드혹적인 성향이 강한 문제. 

 

 

 

지금은 23869 tickets라는 문제를 보고 있다...