220921 문제 풀이 기록

G1 | 18262 - Milk Pumping

풀이 시간: 20분

시도 횟수: 1회

체감 난이도: G2

풀이 쓸 의향: 下

풀이

f 제한 1이상 ~ 1000이상까지 1000번 다익스트라 돌리기

여담: 원래 P5였는데 G2 투표해서 G1으로 만들었음. 쩝,,,

 

 

 

P4 | 5851 - Cow Lineup

풀이 시간: 1시간

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 中

풀이

값 압축 후, 투 포인터로 서로 다른 숫자 개수가 K+1 이하로 유지하며 구간 체크하기.

여담: [l, r] 구간 안에서 서로 다른 숫자 개수를 세그트리로 구할 수 있지 않을까? 하는 생각에 좀 오래 말렸던 것 같음. 근데 찾아보니까 되는 풀이가 맞긴 한데... 어,,,,, 나중에 알아보도록 하자...

 

 

 

P4 | 5852 - Island Travels

풀이 시간: 40분

시도 횟수: 3회

체감 난이도: P4

풀이 쓸 의향: 下

풀이

일단 각 섬들의 번호를 기록한 뒤에, 각 섬에서 다른 섬으로 갈 때 필요한 최소 수영 거리를 계산하고, 해당 값을 바탕으로 시작점 N개에 대해 외판원 순회 문제처럼 비트필드 dp로 최솟값 찾기

여담: 문제 풀이가 바로 떠올라서 "그는 신인가???" 했었는데 구현에서만 35분을 쓰면서 개같이 멸망!! 풀이 자체는 참 어려울 것 없는데 구현해야 할 것들이 너무 많아서 실수했으면 그대로 디버깅의 늪에 빠져 헤멜뻔 했는데, 다행히 별 것 아닌 실수들만 해서 살았다.