220923 문제 풀이 기록

P5 | 5828 - Fuel Economy

풀이 시간: 무려 2시간

시도 횟수: 3회

체감 난이도: 분하게도 P5

풀이 쓸 의향: 下

풀이

i번째 다음으로 작으며 g 범위 안에 있는 다음 위치 nxt[i]를 잘 생각하며 계산하기. nxt[i]가 존재하면 해당 위치까지만 가면 되고, 존재하지 않으면 g만큼 다 사야 함.

여담: Monotone stack을 사용하는 문제였는데, 구현에서 너무 애를 많이 먹어버렸다. 처음에는 deque로 구현해보려 했는데, 구현중 뇌절이 너무 심하게 와서 여러번 틀리고 반례를 너무 늦게 찾아버렸다... 태그 힌트 보고 바로 stack으로 바꿔서 해결하긴 했는데, stack 구현을 n부터 1까지 역순으로 해주는 처리가 인상깊었다.

 

 

 

P4 | 11962 - Counting Haybales

풀이 시간: 35분

시도 횟수: 1회

체감 난이도: 어쩔수 없이 P4

풀이 쓸 의향: 下

풀이

min / sum lazy seg를 구현할 수 있는지를 묻는 문제.

여담: 이번에도 USACO p4 랜덤을 돌렸는데 이런게 나와버렸다. 음... 다음부터는 다시는 안나왔으면 좋겠다. 이런 문제들 자체가 싫다는건 아니고, 그냥 너무 날먹하는 기분밖에 안들어서...