교내 경시 대비 #1

교내 경시를 대비하여 가볍게 돈 셋을 정리하는 글이다. Blackking26과 함께 7월 13일 19시 부터 20시 40분까지 100분 간 진행했다. 문제는 S5~G5 한글 디스크립션 랜덤문제 13문제를 뽑았다. 

100분 동안 11문제를 풀었다. 실버라서 그런지 무난하게 빨리 풀렸다. 사실 좀 많이 쉬웠다. 앞으로는 난이도를 조금 올리는 게 좋을 것 같다. 

A. 삼삼한 수

어떤 수를 3진법으로 나타냈을 때 2가 있는지 확인하자. 예외 처리로 0을 신경써주어야 한다.
정말 간단하게 풀리는 문제

B. 텔레포트

어떤 두 도시를 가는 방법은 그냥 가거나, 출발지 -> 특별한 도시 -> 텔레포트 -> 목적지로 가는 두 가지 방법이 있다. 두번째 방법에서 텔레포트 비용은 항상 일정하기 때문에 모든 도시에 대해서 가장 가까운 특별한 도시까지의 거리를 미리 구해 놓아야 한다. 
생각보다 아이디어를 떠올리는 게 까다로웠다. 아무래도 그래프에 대한 직관성이 많이 떨어진 듯한 느낌?

C. 케이크 자르기

정말 많이 마주친 가장 기본적인 형태의 파라메트릭 서치 문제. 딱히 어려울 것은 없었다. 물론 파라메트릭 서치를 할 때는 항상 +-1을 잘 고려해 주도록 하자.

E. 우유 도시

딱 보자마자 굉장히 무난한 형식의 자주 마주친 DP 문제라는 것을 깨달을 수 있었다. 일단 기본적으로 생각보다 고려해주어야 할 경우의 수가 굉장히 많았다. 
기본적으로 경우의 수를 모두 각각 처리해주는 DP는 코딩을 어떻게 하느냐에 따라서 굉장히 천차만별이다. 나는 보통 복붙을 오지게 때려서 푼다. 이 문제도 2200B 정도의 코드를 짰다. 중요한 점은 문제의 조건을 꼼꼼히 보지 못했다는 점. 덕분에 코드를 싹 바꾸는 과정에서 굉장한 뇌절을 하였다... DP에서는 점화식을 확실히 해야지 대충 넘겨집으면 절대로 안 될 것 같다. 무조건 펜을 잡고 종이에 수식을 적어보기! 끝나고 27초 후에 풀었다. 

F. 30번

그냥 절반씩 줄어드는 것이 딱히 관찰이 어려운 것도 아니고, 굉장히 익숙한 방식이다. 
굉장히 빠르게 풀었다. 물론 다운로드를 받아 문제를 푸는 것이 조금은 독특했다. 그뿐이었다.

G. 타일 채우기 3

정말 쉬운 난이도의 바로 보이는 DP인줄 알았으나, 처음 세운 식대로 짜보니까 예제가 나오지 않았다. DP식이 조금은 까다로웠다. 물론 직접 타일을 그려보니까 직관적으로 바로 나오기는 했지만, 머리로만 풀려고 했으면 생각보다 시간도 오래 걸리고 멘탈이 나갔었을 수도 있다. 핵심은 prefix를 관리하는 것. 익숙하지 않은 입장에서는 삽질을 하기가 쉽다.

H. 줄세우기

딱 보자마자 그냥 inversion counting. 그리고 당연하게도 가장 기본적인 형태의 inversion counting O(N^2)이 되서 정말 편하다.

I. 연산자 끼워넣기 

생각보다 빡쎈 문제. 구현을 하기 나름인 것 같다. 일단 4^10이 가능하다는 것을 생각해야 한다. 나는 재귀에 굉장히 약하기 때문에 재귀로 짰을 때는 계속 틀려서 그냥 4^10을 모두 돌리고, 주어진 연산자만큼만 딱 사용했을 때만 최댓갑스 최솟값을 업데이트 하는 형식으로 했다. 이렇게 하니까 훨씬 편한 것 같다. 

J. 좌표 정렬하기

pair로 묶고 정렬하기. 

K. 백대열 

Do you know __gcd ?

L. 슬라임 합치기

코포에 나올법한 문제. 잘 생각하면 임의의 두 수가 다른 그룹에 있다가 같은 그룹으로 될 때 a*b 가 전체 답에 더해지기 때문에 값은 항상 임의의 두 수를 곱한 값의 합으로 나오게 된다. 많이 해봤기 때문에 쉬운 관찰

M. 과자 나눠주기

이 역시 굉장히 무난한 파라메트릭 서치 문제.

정리

지금까지 문제를 930문제나 풀었다. 그러다 보니까 왠만한 문제는 그냥 보이는 것 같다. 이 정도 수준의 문제에 대한 관찰은 거의 바로 이루어진다. 거의 뎅겅파라고 할 수 있다. 하지만 구현 단계에서는 가끔씩 미숙한 모습을 간간히 보였다. 당연히 쉬운 구현방법이 있는데도 돌아간다. 그렇다고 쉬운 구현방법을 생각하는데 얼마나 시간을 들여야 할지도 잘 모르겠다. 이 부분은 계속 연습을 하면서 생각해나갈 부분이다. 
그리고 문제의 난이도가 전체적으로 너무 쉬웠다. 아무리 교내경시가 쉽게 나온다고 해도 절대로 이정도로 쉽지는 않다. 다음에는 난이도를 좀 높여서 다시 할 예정이다.