삼성 대학생 프로그래밍 경진 대회(SCPC) 2017 1차 예선 후기

이제 scpc도 3년 차!

1, 2, 4번은 오전에 문제 읽고 풀이가 바로 떠올라서 오후에 바로 구현하였고

3번은 처음에 2-sat인가 했지만 2-cnf식이 안 떠올라서 고민하다가 2-cnf식으로 변형이 되어서 2-sat으로 풀었다.

5번은 정말 도통 몰랐는데 6명 정도 만점을 받은 것 보니 갓 문제였던 것 같고 더 공부해야겠다!!

1번은 스택을 이용해서 풀었고

2번은 그리디를 이용했는데 반밖에 증명을 안 했다 더 생각 해봐야겠다.

3번은 전구가 켜저있거나 꺼져있을 때에 따라 스위치들의 2-cnf식을 세울 수 있고 따라서 2-sat으로 풀 수 있다.

4번은 주어진 단순다각형을 단조 다각형으로 판별할 수 없는 방향벡터 d의 범위는 오목 꼭짓점에서 정의 될 수 있다.

따라서 모든 오목 꼭짓점에서 안되는 범위들을 모으고 이 범위가 [0,2pi)를 다 덮는지 확인하고 답을 출력했다.