2020 한국 정보 올림피아드 1차 후기 및 간단 풀이

정말 중요한 시험... 입시로 굉장히 바쁜 때였지만, 포기할 수 없었다. 2년간 1차 탈락을 한 슬픔을 만회할 수 있는 마지막 기회였다. 그래서 최근 1주일동안 열심히 준비를 했다.

시간이 없기 때문에 1교시 문제는 다루지 않고 2교시 실기 문제만 다루려고 한다.

1교시를 1~2개 빼고 다 맞은 것 같아서 기분이 좋은 상태로 시작하였다. 특히 비버챌린지 4번을 1초 남기고 137의 경로를 찍고 제출을 해서 굉장히 행복한 상태였다.

문제는 여기서 볼 수 있다.

1번 박 터트리기

풀이

서로 다른 수 M개의 합으로 어떠한 수를 표현할때는 연속된 M개의 수로 표현이 가능하거나 중간에 1개를 띄고 M개로 표현이 가능하다. 즉 4개의 합으로 14를 표현할때는 2 3 4 5, 15를 표현하려면 2 3 4 6, 16을 표현하려면 2 3 5 6. 이런식으로 말이다. 또한 최댓값과 최솟값의 차이가 가장 적은 경우는 이 경우라는 것을 알 수 있다. 

따라서 N이 1에서 M까지의 합보다 큰지, 연속된 M개의 합으로 나타낼 수 있는지. 의 두 번의 분별을 통해서 수를 3가지로 분류가 가능하다.

1번 후기

이거 완전 div 1 코포 C에서 봤던 느낌의 문제였다. 물론 엄청난 하위호환이었다. 정말 쉬운 문제였다... 이게 정말 1번이 맞나 싶었다. 작년에 2교시 1번을 못푼 내가 너무나도 미워졌지만, 지금은 그럴때가 아니었고, 바로 구현했다. 10줄도 안되는 코딩으로 구현이 가능해서 구현미스가 날 일도 없었다. 2분만에 푸는데에 성공했다.

 2번 햄버거 분배

풀이

사람들을 순서대로 생각해보자. 가장 왼쪽에 있는 사람은 먹을 수 있는 구역이 가장 왼쪽으로 치우쳐져 있으므로, 자신이 먹을 수 있는 햄버거 중 가장 왼쪽 햄버거를 먹는 것이 이득일 것이다. 그렇게 생각하면 당연히 더 왼쪽에 있는 사람이 더 왼쪽 햄버거를 선택하는 것은 당연하다

따라서 왼쪽부터 순서대로 스위핑을 하면서 사람에게 먹을 수 있는 가장 왼쪽 햄버거를 매칭시켜주면 된다.

2번 후기

이게 2번이 맞나 싶었다. 코포 div2 B나 해봤자 C에 나올법한 정말 직관적으로 관찰이 되는 그리디 문제였다. 바로 뚝딱 구현하기 시작. 이번에도 구현에 문제 없이 AC를 받을 수 있었다. 이때까지 걸린 시간 단 8분

3번 조명등

풀이

점 들이 . . .   . .   막 있고 이것을 연속된 그룹으로 묶어야 한다. (. .. ..)(..)(.) 이런식으로 말이다. 이런 유형의 문제를 보면 보통 DP라는 생각이 들게 된다. DP[i]를 i번 조각품까지 조명등으로 비췄을때까지 최소 비용으로 설정한다. 그러면 $DP[i]=\underset{j\leq i}{min}(DP[j-1]+sol(j,i))$ 이 된다. 이때 sol(j,i)는 j번 조각품 부터 i번 조각품까지 모두 덮는 조명등의 최소 비용이다.

위의 식은$O(N^2)$으로 해결할 수 있다. 하지만 우리의 목표는 $O(NlgN)$이다. DP...NlgN...저런 형태의 식... 와! 이건 알만한 사람들은 바로 CHT를 떠올렸을 것이다.(CHT롤 모른다면 이 글) 그래서 이 문제는 CHT로 해결할 수 있다. 

이제 sol(j,i)에 대해서 생각을 해봐야 한다. sol(j,i)에서 가장 중요한 것은 j와 i사이에 있는 가장 y-x가 큰 점과 가장 x+y가 큰 점이다. 이를 좀 더 편하게 생각하기 위해서 좌표를 90도 돌려준다. 그리고 나서 회전한 좌표축에 대해서 정렬을 하면 순서대로 조명을 넣어줄 수가 있다. 

이때 구현의 편의나 알고리즘의 정당성을 위해서 a를 조명으로 비출 때 무조건 b도 같이 비춰진다면, 그러한 b들을 없애줄 것이다. 이 과정은 segment tree를 이용해서 간단하게 처리할 수 있다. inversion counting을 하는 방법을 알고 있다면 쉽게 떠올릴 수 있을 것이다.

3번 후기

나는 DP를 정말 많이 했기 때문에 보자마나 DP를 의심했다. 하지만 나는 1 2번을 8분 컷햇길래, 그리디의 호기심을 풀어내야만 했다. 앞에서부터 묶는게 이득이면 묶어서 비추고 아니면 따로 비추는 방식으로 코딩을 했고 이것이 풀이 A였다. 결과는 19점. 여기서 반대로 뒤집어서 한 번 더 해봤다. 이것이 풀이 B였고, A와 B를 합친결과 33점이 나왔다. 사실 조금만 생각해도 그리디가 안된다는 것을 알 수 있었다. 반례를 생각할 수 있었지만 왜 홀렸는지 모르겠다.

DP? nlogn? 문제 형태? CHT! 바로 결론이 났다. 그리고 또 낸 하나의 결론은 망했다. 였다... dp opt가 생으로 나오지는 않을 것이라고 확신하며 내 블로그 dp opt 정독하는 것을 하지 않앗기 때문이다. 물론 기억 조각을 모아서 풀 수는 있었다. 
하지만 나는 좌표계를 90도 돌리는 방식을 생각하지 못하였다. 즉, 정렬기준을 제대로 생각하지 못하여 sol(j,i)를 어떻게 처리해야할지 몰랐었다. 당연히 모든 h가 같을때는 cht로 풀 수 있었지만, 그게 아닌 경우는 해결할 수 없었다.

여기서 내린 나의 결론은 긁는 것이었다. n<=1000을 긁으면 그 안에 h가 같은 것도 포함되어있을테니 h가 같은 것을 맞기 위하여 바로 구현이 되지 않는 cht를 짜는 것은 좋은 방향이 아니라고 생각했다. 그래서 나는 일단 n<=1000을 짜기 시작했다. 나는 완성했고, 이것이 풀이 C였다. 결과는 37점

cht 였지만, 관찰을 통해서 i가 증가할 수록 dp[i]가 최솟값이 나올때 마지막으로 i랑 같이 묶는 시작점 j도 증가할 것이라는 가설을 세웠다. 물론 정확히 구해진 하에서 하는 것은 아니기 때문에 DNC opt를 할 수는 없었지만, 대략 비슷하게 따라할 수 있었다. 사실상 커팅의 영역. 이 풀이 D로 받은 점수는 49점

이제 범위에 따라서 풀이를 합치는 일 밖에 안남았다. 아.... 왜 컨트롤 z도 안되고 코드 복붙해놓은 것은 날라갔는가... 풀이 A,B코드가 날라갔다. 그래서 다시 짰다. 합체를 하고 범위를 잘 조정해 주니 점수는 64점!

이제 마지막 제출 이분탐색의 영역으로 넘어갔다. 제일 아쉬웠던 부분은 D로 풀때는 14,15,16,17,18을 맞았는데 합치니까 틀렸던점. 그래서 찍신을 통해서 t%3==0인 경우가 17번 테케 하나라는 것을 알아냈다. 그래서 t%3==0 일때만 D 풀이 하나만 쓰도록 코드를 조정하였다. 결과는 TLE... 뭐지.... 그렇게 결국 264로 마무리 하였다. 

괜히 CHT 짜다가 뇌절이 충분히 올만한 시험이었다. 애초에 90도 돌리는 테크닉을 생각조차 하지 못했기 때문에 나는 충분히 내가 할 수 있는 최선을 다했다고 생각한다. 풀이의 합집합!!! 조금의 아쉬움은 있었지만, 지난 2년간의 설움을 지워버릴만큼은 충분히 만족한 이번 대회였다.