221206 / 221207 문제 풀이 기록

P3 | 20945 - 의자 게임

풀이 시간: 1시간 + a

시도 횟수: 2회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

문제를 정리하면, 반복되는 수 없이, 최대-최소 차이가 K이하인 최대 크기를 x라 하면, 답은 K-max(x)이다. 반복되는 수 없음은 set을 사용하여 구현하였고, 최대-최소 차이는 segtree와 단조성을 활용한 이분탐색으로 구현하였다.

여담: 처음에 아예 틀리게 생각했었는데, 그 풀이에서 조금씩 뻗어가면서 풀이에 접근해갔다. set 안쓰고 무지성 n^2으로(미쳤었던듯) 제출했다가 TLE 한번 뜨고, 다시 set으로 구현해서 AC.

 

 

 

P3 | 23834 - 커여운 키위

풀이 시간: 45분?

시도 횟수: 2회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

dp[i] = i번째에서 음수로 이동하는 경우의 이동 거리 최댓값 으로 정의하자.

그러면, dp[i] = max(dp[j] + sum[i-1] - sum[j]) - a[i] = max(dp[j] - sum[j]) + sum[i-1] - a[i] for i-m <= j < i 로 정의되고, dp[j] - sum[j]값을 segtree를 활용하여 저장해주면 답은 max(dp[i] + sum[i+m] - sum[i] + b[i], sum[i] - sum[j] + dp[j] for j<i) 이다.

여담: segtree + dp 유형의 문제. 태그를 보니까 덱을 이용한 dp라고도 하던데... 세그트리가 참 만능인듯 싶다.