[SCPC] 삼성 제 3회 SCPC 1차 이야기

당일 시험 친 후 올리려했는데 미루고 미루다보니 이제 쓰게 되었다.

17년 6월 30일 오전 10시 ~ 17년 7월 1일 오전 10시까지

총 24시간 진행된 SCPC 1차 시험은 생각보다 어려웠다.

문제를 푸는데 작년에는 물론 1문제 밖에 못풀었지만(알고리즘을 알던 시절이 아니었다.)

1문제를 풀고 100점을 받고도 2차를 갔었는데 이번에 다시 풀어보니 왠만한건 풀 수 있었다.(작년 문제)

그런데 이번에 문제는... 어떻게 말하면 정말 문제를 잘만드는구나였고 어떻게 말하면 문제에 함정투성이었던 것같다.

1번문제는 특히 괄호에 대한 처리문제였는데 스택으로 해결될 줄 알았지만 전혀 그렇지 못했고,

최종적으로 DP + 스택으로 문제를 해결하였다.

문제는 SCPC가 끝나면 '괄호'라는 문제를 참조해보길 바란다.

2번 문제는 사고팔고하는 문제였는데 이 문제는 기울기로 접근하면 쉽게 풀 수 있었다.

차라리 1번보다 2번이 더 쉬운 이번 SCPC였다.

1, 2번 모두 O(n)에 문제를 해결 할 수 있다.

3번문제부터가 문제였다.

n*n에 있는 모든 전구를 다켜야하는데 2-SAT로 푸는 문제라하였다.

나는 백트래킹으로 문제를 해결하려 했지만, 계속해서 틀렸기에 포기했다.

4번 문제는 기하문제였는데

CCW로 허무하게 해결할 수 있다는 소문이 있다.

나는 도형의 넓이 != 벡터 외적을 이용한 넓이 일때 단순 다각형이 아니라 단조 다각형이라 생각했는데

생각해보니 단조 다각형의 도형 넓이를 구할 방법이 없어서 풀지 못하였다.(물론 기하를 잘 모른다.)

5번 문제는 보지도 못했지만 LCA문제라고 한다.

최종적으로 200점을받았는데 아마 2차는 충분히 올라갈 듯하다.

본선을 가는 티켓이 너무 가지고 싶은데 잘 치면 좋겠다..