Logo냥냠감자기술 블로그
Skip to Content
AlgorithmGreedy (14)구두 수선공
작성일: 2024-01-12

문제

백준 14908 - 구두 수선공 

  • 난이도: 골드1
  • 알고리즘: 그리디

코드

#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Info { int time; int cost; int index; bool operator<(Info& next); }; bool Info::operator<(Info& next) { if(cost*next.time<next.cost*time) { return true; } else if(cost*next.time>next.cost*time) { return false; } else { return index>next.index; } } int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int taskNum; cin>>taskNum; vector<Info> infos(taskNum); for(int i=0; i<taskNum; i++) { cin>>infos[i].time>>infos[i].cost; infos[i].index=i+1; } sort(infos.begin(), infos.end()); for(int i=taskNum-1; i>=0; i--) { cout<<infos[i].index<<" "; } }

회고

두 작업 시간을 T1, T2 두 작업을 하지 않았을 때 하루 당 보상금을 S1, S2라고 했을 때, 첫번째 작업을 먼저 할 경우 보상금은 T1 * S2 이고, 두번째 작업을 먼저할 경우는 T2 * S1이다. 또한 만일 T1 * S2(S1를 먼저 할 경우) > T2 * S1(S2를 먼저 할 경우) && T2 * S3(S2를 먼저할 경우) > T3 * S2(S3를 먼저 할 경우) 일 경우 T1 * S3(S1을 먼저 할 경우) > T3 * S1(S3를 먼저 할 경우)는 자동으로 성립한다. 이에 따라 대소 비교 함수를 작성하였다. 이때 값이 같다면 오름차순으로 가장 먼저 출력되는 순서를 찾기 위해 인덱스 비교도 하였다.