반응형 PS1 SCPC 2023 1차 예선 후기 1번 브루트포스로 최댓값 찾으면 된다. 2번 방향 전환을 여러 번 하는 것은 의미가 없다. 어차피 가장 먼 곳까지 가는 길 중간에 다 수확 가능하기 때문이다. 따라서 한 방향으로 맥시멈까지 갔다가 반대방향으로 전환해서 남은 이동거리만큼 최대한 가면 된다. 맥시멈 정하기는 O(N)에 할 수 있고, 맥시멈까지 가면서 수확할 수 있는 양은 정렬 후 이분탐색으로 O(logN)에 구할 수 있으므로 총 시간복잡도 O(NlogN)에 해결가능하다. 1. 왼쪽 먼저 가기 → -(lmax)까지 갔다가 +(D-2*lmax)까지 가기 2. 오른쪽 먼저 가기 → +(rmax)까지 갔다가 -(D-2*rmax)까지 가기 3번 시뮬레이션할수록 빈 바구니가 줄어들게 된다. 따라서 '총 구슬 개수의 합'이 '바구니 개수'보다 크거나 같.. 2023. 8. 3. 이전 1 다음 반응형
