220925 문제 풀이 기록

P3 | 5896 - 효율적으로 소 사기

풀이 시간: 약 1시간 30분 + a

시도 횟수: 4회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

쿠폰 오름차순 / 일반가 오름차순 각각의 pq 두개 만들어두고, 쿠폰 오름차순부터 차례대로 보면서 최소값으로만 고르기

여담: pq 심화 문제였는데, 너무 헤맸다... 너무 그리디를 다른 방식으로만 생각한 것 같다.

 

 

 

P3 | 5910 - Mountain Climbing

풀이 시간: 1시간 20분

시도 횟수: 3회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

down>=up과 down<up 두 가지로 나눠보면 down>=up인것 우선으로, down>=up이면 up 오름차순 / down<up이면 down 내림차순 정렬하여 둔 것이 최적이라는 사실을 증명한 뒤에 구현하기

여담: 대체 이걸 어떻게 생각해야 할지 감도 안와서 문제 풀다 잠깐 쉬고 와서 다시 풀었다. 오늘 푼 그리디 두 문제 모두 내가 지금까지 봐왔던 그리디랑은 조금 다른 형태의 그리디였는데, 한 관찰에서 20분 이상 생각하지 말고 20분 넘게 관찰하다가 해당 방향으로 관찰이 힘들면 다른 방식으로 관찰해야겠다. 이 문제를 풀 때는 반드시 down이 연속적으로 되면 맨 앞의 up + sum(down)일 것인데, 이때 up을 어떻게 구할지 내지는 down이 어떻게 연속이 될 수 있을지를 보고 있었는데, 결과적으로는 아예 쓸데없는 관찰이었다.