Hyun's_Devlog

https://www.acmicpc.net/problem/1700

풀이 방법

핵심은 콘센트가 가득 차있을 경우 어떤 전기용품을 뺄지를 결정하는 것이다.

정답은 앞으로 사용하지 않을 기기 혹은 앞으로 사용할 예정인 기기로 가득 차있는 경우라면 그중에서 가장 나중에 사용할 기기를 빼면 된다.

질문게시판에 좋은 예제가 있어 해당 예제로 설명하면 다음과 같이 동작한다.

3 10
1 2 3 4 4 5 2 1 1 4

정답 코드

https://www.acmicpc.net/problem/14464

그리디 문제다. 

풀이

소와 닭의 이동시간을 비교해서 조건이 맞는 경우를 세는 문제다. 단, 여기서 중요한 점은 소의 이동가능시간이다. 해당 부분의 정렬 조건에 대해 생각하는 데에 오랜 시간이 걸렸다. 

닭 i가 소 A와 소 B 두 마리 모두 데려다줄 수 있는 경우, 둘 중 이동 가능 시간의 범위가 더 좁은 경우를 우선적으로 선택해야 선택받지 못한 소를 다음 순번의 닭이 데려다줄 가능성이 더 높아지게 된다. 즉 닭의 시간을 오름차순 정렬, 소의 이동시간이 짧은 순서 & 움직이기 시작한 시간이 오름차순으로 정렬이 되어야 한다는 이야기다.

소의 움직임이 완료된 시간을 기준으로 오름차순, 움직임이 완료된 시간이 같다면 움직이기 시작한 시간 기준으로 오름차순으로 정렬한 뒤, 오름차순으로 정렬된 닭의 시간을 기준으로 데려갈 수 있는 소들을 탐색하여 접근하였다.

정답 코드