BOJ 14908 구두 수선공

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/14908

🧐 관찰 및 접근

#

• 직관적으로 생각해보자
  • 어떤 작업의 보상금 $S_i$가 크다면, 빠르게 작업을 수행하는게 좋다.
  • 어떤 작업을 완료하는데 걸리는 시간 $T_i$가 작다면, 빠르게 작업을 수행하는게 좋다.
    • 이 두가지를 어떻게 동시에 활용할 수 있을까?
• 어떤 정답 $Opt$가 존재한다고 가정해보자.
  • 이때, $Opt$의 순서중 가운데 두 작업 $W_i, W_{i+1}$을 바꾼다고 해보자.
    • 이 때, 바뀐 순서 $Opt'$가 $Opt$보다 나을 수 있을까?
    • 두 작업을 바꾸면, $Opt' = Opt + S_i * T_{i+1} - S_{i+1} * T_i$가 된다.
    • 다시말해, $S_i * T_{i+1} - S_{i+1} * T_i$ 이 음수라면 더 나은 해법을 찾을 수 있다.
    • 따라서 $S_i * T_{i+1} - S_{i+1} * T_i > 0$인 방향,
    • 즉 $\frac{S_i}{T_i} \geq \frac{S_{i+1}}{T_{i+1}}$ 의 순서로 정렬하면 최적해가 된다.

💻 풀이

#

• 코드 (C++):

void solve(){
    int N; cin >> N;
    vector<array<int, 3>> ans; // S, T, idx;
    rep(i, 0, N){
        int S, T; cin >> S >> T;
        ans.push_back({T, S, i+1});
    }
    sort(all(ans), [](const array<int, 3> &a, const array<int, 3> &b){
        if(a[0]*b[1] == a[1]*b[0]) return a[2] < b[2];
        return a[0]*b[1] > a[1]*b[0];
    });
    for(auto &p: ans) cout << p[2] << ' ';
}