나는 초등학생때부터 정보올림피아드를 나가고 있다.
사실 어쩌다 보니 격년으로 치듯이 되버렸는데,
따라서 변경 후의 19년 정보올림피아드에 나가본 적이 없다
18년 정보올림피아드와 비교한 후기가 될 것 같다.
우선 1교시는 80분짜리 필기시험이다.
문제는 20문제 주어지는데
시간이 개인적으로는 좀 빡빡했다.
한 네다섯문제 가까이 틀린거같다.
문제의 난이도 자체는 그리 어려운거 같지는 않은데
최적의 답안을 요구하는 문제들에서
이 답이 최적이 맞는지를 모르기 때문에 그냥 적당히 최적해인것처럼 보이는 걸 내서
많이 틀린거 같다.
18년 정보올림피아드는 프로그램의 실행결과를 묻는 문제가 많았지만,
올해는 앞부분의 수학문제가 많아진거같은 느낌이다
노가다가 심한 문제가 몇 있었고,
규칙을 찾으면 쉽게 풀 수 있는 문제가 좀 있었다.
2교시는 100분짜리 실기다.
18년당시에는 실기가 따로 없었기 때문에 비교할만한 대조군이 없다.
작년에도 나간 사람들이 말하길 올해는 작년에 대비해서 엄청나게 쉽다는 평이 많았다.
실제로 나도 좀 빠르게 푼 거 같다.
1차대회에서 변별력을 높이기 위해 이번에는 세문제가 주어졌다.
1번은 그리디하게 접근해서
k*(k+1)/2 > N인지를 판별해서 만약 N이 더 작다면 -1을 출력해주면 되고,
0 1 2 3 . . . k 개의 공이 담긴 바구니를 미리 준비한다음
가장 많은 공이 담긴 바구니부터 N-(k*(k-1/2)개를 배분해주는데
만약 가장 적은 공이 담긴 바구니에 도달하면 다시 가장 많은 공이 담긴 바구니부터 순회하면 된다.
그럼 항상 arr[0] < arr[1] < arr[2] ... arr[k-1] 이 되기 때문에 조건에 부합하며,
O(N)에 해결할수 있다.
2번은 그냥 완전탐색으로도 가능했다.
여기서 조심할만한건 그냥 탐색할때
i-k부터 i+k까지 탐색하는데,
i-k이 음수이거나 i+k가 N의 범위를 벗어나는 경우에 대한 처리가 필요하다
그리고 하나의 햄버거를 둘이먹는게 불가능하므로
arr[i] == 'P' 인 i에 대해서
i-k부터 i+k까지 포문을 돌리면서
가장 먼저 찾은 햄버거를 먹는다는 표시를 해주고( arr[j] = 'x'. H이거나 P만 아니면 뭐든 상관없다. )
탈출해준다.
이러면 O(KN)시간복잡도가 되므로
제한시간 안에 문제를 해결할 수 있다.
여기까지 푸는데 대략 한시간 정도 걸렸다.
3번을 남은시간동안 계속 고민해봤는데
어떻게 접근해야할지조차 제대로 알수가 없었다;;
시험 끝나고 반응을 들어봐도 대부분 3번은 풀지 못하신거같아서
명확한 해답은 아직도 모르고있는 상태다.
결과적으로 500점만점에 350점 언저리가 나오지 않을까 예상을 해보고 있는데
본선 갈수 있었으면 좋겠다 :)
- CHT 알고리즘이라고 하더라...
가채점결과는 예선 탈락.
336 / 500으로
일반고부문 13.785%
전체부문 27.829%
