2020 중앙대학교 프로그래밍 경진대회(CPC) 풀이
백준20205 교수님 그림이 깨지는데요?
단순 구현 문제입니다.
백준20206 푸앙이 길을 건너간 이유
이쁘게 구현할 방법이 떠오르지 않아서 ccw로 선분 교차 여부를 확인했습니다.
직선의 x좌표는 $[-10^9, 10^9]$ 정도만 고려해도 충분합니다. a 혹은 b가 0인 경우를 주의해야 합니다.
백준20207 달력
단순 구현 문제입니다.
백준20208 진우의 민트초코우유
고려해야할 지점이 최대 10개이므로, $N!$가지의 모든 방문 순서에 대해 먹을 수 있는 우유의 최대 개수를 구해주면 됩니다.
백준20209 스트레이트 스위치 게임
가능한 상태는 $5^N$가지입니다. 각 상태를 정점으로 표현한 그래프 위에서 BFS를 돌리면 됩니다.
백준20210 파일 탐색기
단순 구현 문제입니다.
백준20211 게임 개발자 영우
X값을 고정하면 가능한 Y값은 0개 혹은 1개 밖에 없습니다.
N 이하의 모든 자연수 X에 대해 가능한 Y값을 구하는 방식으로 접근합시다.
Prefix Sum과 Parametric Search를 이용해 레벨업 하는 지점을 찾아서, N번째 사냥으로 인해 레벨업 되는지 확인하면 됩니다. N번째 사냥으로 인해 레벨업이 된다면 그 레벨이 Y값이 되고, 그렇지 않다면 가능한 Y가 존재하지 않습니다.
매 사냥마다 경험치를 1 이상 얻기 때문에, X가 주어졌을 때 N/X번 레벨업 합니다.
$N/1 + N/2 + N/3 + \ldots + N/N = O(N \log N)$이므로 Parametric Search를 $O(N \log N)$번 수행합니다. 따라서 전체 시간 복잡도는 $O(N \log^2 N)$이 됩니다.
백준20212 나무는 쿼리를 싫어해~
쿼리 정렬하고 Dynamic Segment Tree를 짜면 됩니다.