그리디 (멀티탭 스케줄링)

여태까지 중에 백준에서 가장많이 틀리고 다시 시도한 문제

내가 생각한 방식에 대한 믿음을 가지고 풀어야 풀리는 듯. 증명하라고 하면 절대 못할 것 같다.

 

풀이방식

1.  처음에 플러그가 다 채워질 때까지 장비를 꽂는다.

2. 이미 꽂혀있는 장비라면 건너뛴다.

3. 플러그가 다 꽂혀있고 이미 꽂혀있지 않은 장비라면 

   3-1. 후에 다시 쓰지 않는 장비를 빼고 그 자리에 꽂는다.

   3-2. 다시 쓰지 않는 장비가 없다면 가장 나중에 쓰는 장비부터 빼고 그 자리에 꽂는다.

 

처음에는 나중에 쓰는 장비의 빈도수를 계산해서 가장 적게 쓰는 장비부터 빼면 된다고 생각했는데 이건 틀렸다.

그 이후에도 자잘하게 놓치는 부분이랑 인덱스 계산 오류 등등 실수가 많았다.

매우 까다로운 문제.