[Algorithm] Microwaving Lunch Boxes (Algospot – LUNCHBOX)

By | 2018-09-03

출처

  • https://algospot.com/judge/problem/read/LUNCHBOX
  • 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 (구종만)

난이도

  • (하) – 중 – 상 – 최상 – 풀지못함

문제

  •  N개의 도시락을 데우는 시간과 먹는 시간이 주어진다. 도시락을 데울 수 있는 전자레인지가 1개 밖에 없다고 가정을 했을 때 모든 도시락을 다 데워서 먹는데 걸리는 최소한의 시간을 찾는 문제이다. 도시락은 무조건 한 번에 다 데워야 한다는 가정이 있다. 다시 말해서 중간에 멈췄다가 다시 데우면 처음부터 다시 데워야 한다는 의미이다.

후기

  • 알고리즘 책에서 제공하는 문제이다. 항상 CH가 나누어져 있어서 당연히 탐욕법을 이용해서 문제를 풀어야 한다는 건 알고 있었다. 그래서 그런지 생각보다 문제가 너무 쉽게 풀렸다.
  • 어떠한 순서로 도시락을 데워도 도시락을 데우는 시간은 절대로 변하지 않는다. 다시 말해서 도시락을 데우는 순서가 중요한 게 아니라, 먹는 속도가 중요하다는 의미이다. 그래서 도시락을 늦게 먹는 시간순으로 정렬을 하고 먹는 데 오랜 시간이 걸리는 도시락부터 순서대로 도시락을 데워서 먹으면 된다.
  • 나의 경우 작은 수부터 나열하여서 역순으로 사용했다. 하지만, 책에서는 양수를 모두 음수로 만들어서 Sort 함수를 사용하면 큰 숫자 (큰 수가 제일 작은 수가 됨)부터 정렬된다. 계산할 때 숫자에 단순히 -1을 곱해서 사용하면 된다.

코드

  • 탐욕법을 사용한 코드
  • Github 주소: https://github.com/mkblog-cokr/algorithmCode
  • 실행 시간: 40ms (제일 빠른 코드 대비 대략 5배 (8ms) 느림)

 

Leave a Reply

Your email address will not be published. Required fields are marked *