2021 KOI 대비 DAY-1

 오랜만에 글을 쓴다. 지난 일주일 동안 열심히 노느라 PS에도, 블로그에도 조금 소홀했다. 저녁시간에 축구 또는 농구를 하고 조기 입실을 한 다음, 라면과 컵밥을 먹고 게임을 하다가 11시 조금 넘어서 올라오는 웹툰을 보면서 잠드는 행복한 일상의 반복이었다.

 물론 PS를 완전 놓지는 않았다! 레이지 세그 구현체를 만들려고 보니 전부 탑다운 세그 트리를 이용하길래 탑다운 세그 트리 구현체를 먼저 만들려고 시도했지만, 마음에 드는 구현체를 만들기가 쉽지 않아 포기했을 뿐이다. (struct에 나름 최적화가 되어있으면서도 직관적으로 이해 가능한 그런 구현체가 있다면 공유 부탁드립니다 ㅠ)

 

 정신을 차리고 보니 KOI 예선이 2주 앞으로 다가와서 정말 대비를 해야겠다고 생각하던 차에, 북곽 선생님들께서 졸업하신 선배분들과의 톡방을 만들어주셨다! 실력이 정말 좋으신 선배들이셔서, 많이 배울 수 있는 기회가 될 것 같다. (그러나 톡방이 조용하다) 더불어, 백준에 그룹을 만들어서 KOI 예선 기출문제들을 연습으로 올려주셨다. 이번 글은 연습 문제들 풀이를 간단하게 쓰는 것으로 마치고, 앞으로 올라올 문제들도 가능한 풀이를 써보도록 노력하겠다.

 

 

A - 햄버거 분배

햄버거의 인덱스와 사람의 인덱스를 나누어서 저장한다. 최대한 많은 사람에게 햄버거를 1개씩 매칭시켜야 하는데, 앞의 사람부터 차곡차곡 매칭시키는 것이 최적이다. 각각의 iterator을 관리해주면서 답을 구해준다.

 

B - 줄 세우기

셋에서 가장 어려운 문제. 사람을 원하는 곳으로 보낼 수 있다면 LIS의 길이를 구해야 하는 것이 자명하다. 하지만 양 끝으로만 보낼 수 있으므로, 수가 연속하게 존재하는 LIS의 길이를 구해야 한다는 것을 관찰할 수 있다(찍었다). 이걸 최대 O(NlogN)에 구해야 하는데, O(N) dp가 가능하다는 것을 알 수 있다. 구현은 가장 간단하다.

 

C - 사냥꾼

x좌표를 정렬한 다음 lower_bound와 upper_bound를 적절히 이용하면 된다. 이분탐색 연습문제 정도로 알고 있었는데, 난이도 투표를 보니 O(N) 슬라이딩 윈도우에도 가능하다고 한다.

 

D - 쇠막대기

막대의 개수를 관리해주면서 '()'가 나올 때마다 잘리는 막대의 개수를 누적하면 된다.