2010년 라운드 1C. 캡 쉽다는 말에 유진이형과 연습 돌았었다. 코드는 회사에 있는 관계로 립코딩.
A: Rope Internet
구현. 이보다 쉬울 수 없다. 그냥 n^2 로 짜면 됨.
B: Load Testing
퍼즐스러운 문제. 바이너리 서치랑 거의 비슷. 예제에 대해 손으로 풀어보면서 감을 잡으면 된다. 다시 구현해볼 필요가 있을지도..
C: Making Chess Boards
여러 개의 트릭이 필요한 구현 문제. 체스보드의 크기는 dp 로 구하고, 잘라내는 건 무식하게 잘라내도 된다 (amortized N^2). 잘라낼 수 있는지 체크는 각 모서리를 뒤지면 O(1) 에 할 수 있다. 그리고 후보를 찾는 과정은 priority queue 를 이용해 해결.
사실 난 그냥 존내 무식하게 풀었는데 금방 나오던데? [...]
