JOI Spring Camp 2016 풀이
JOI Spring Camp 2016 풀이Available on AtCoder.Day 1Matryoshka지름 Ri, 높이 Hi인 마트료시카 안에는 지름과 높이가 둘 다 작은 마트료시카를 최대 한 개 넣을 수 있다. 그리고 이것이 중첩이 가능하다. 다른 마트료시카에 들어가지 않는 마트료시카를 바깥 마트료시카라고 하자.어떠한 마트료시카들의 집합이 있을 때, 여기서의 바깥 마트료시카의 최소 갯수를 구하는 방법에 대해 생각해보자. 잘 생각해보면, 바깥 마트료시카의 갯수가 많아지는 이유는 마트료시카들이 같은 마트료시카에 들어가지 못해서이다. 즉, 마트료시카 중 몇 개를 선택하여 그 집합을 S라고 할 때, S에 속하는 마트료시카들이 모두 서로 포함할 수 없다면, 이들은 모두 서로 다른 바깥 마트료시카에 들어가야 ..
2017. 1. 21. 01:42