[백준 24770] Carousel Rides (C#, C++) - soo:bak

작성일 :

문제 링크

24770번 - Carousel Rides

설명

여러 개의 티켓 묶음이 주어집니다. 각 묶음은 a장에 b달러입니다. 카를은 최대 m장까지만 한 번에 살 의향이 있습니다.

조건을 만족하는 묶음 중 1장당 가격이 가장 낮은 묶음을 고릅니다. 1장당 가격이 같다면 티켓 장수가 더 많은 묶음을 고릅니다. 적합한 묶음이 없으면 해당 메시지를 출력합니다.


접근법

먼저, 1장당 가격을 비교할 때 나눗셈을 사용하면 부동소수점 오차가 발생할 수 있습니다. 대신 교차 곱으로 비교합니다. 두 묶음의 1장당 가격을 비교할 때, b1 나누기 a1과 b2 나누기 a2를 비교하는 대신 b1 곱하기 a2와 b2 곱하기 a1을 비교합니다.

다음으로, a가 m 이하인 묶음만 후보로 고려합니다. 후보 중에서 교차 곱이 더 작으면 더 저렴한 것이므로 교체합니다. 가격이 같다면 장수가 더 많은 묶음을 선택합니다.

모든 후보를 순회한 뒤 최적이 있으면 결과를 출력하고, 없으면 적합한 묶음이 없다는 메시지를 출력합니다.


Code

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      while (true) {
        var first = Console.ReadLine()!.Split();
        var n = int.Parse(first[0]);
        var m = int.Parse(first[1]);
        if (n == 0 && m == 0)
          break;

        var bestA = int.MaxValue;
        var bestB = int.MaxValue;
        var has = false;

        for (var i = 0; i < n; i++) {
          var line = Console.ReadLine()!.Split();
          var a = int.Parse(line[0]);
          var b = int.Parse(line[1]);
          if (a > m)
            continue;

          if (!has) {
            bestA = a;
            bestB = b;
            has = true;
          } else {
            var lhs = (long)b * bestA;
            var rhs = (long)bestB * a;
            if (lhs < rhs || (lhs == rhs && a > bestA)) {
              bestA = a;
              bestB = b;
            }
          }
        }

        if (has) Console.WriteLine($"Buy {bestA} tickets for ${bestB}");
        else Console.WriteLine("No suitable tickets offered");
      }
    }
  }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  while (cin >> n >> m) {
    if (n == 0 && m == 0)
      break;

    bool has = false;
    int bestA = 0, bestB = 0;

    for (int i = 0; i < n; i++) {
      int a, b; cin >> a >> b;
      if (a > m)
        continue;

      if (!has) {
        bestA = a;
        bestB = b;
        has = true;
      } else {
        ll lhs = (ll)b * bestA;
        ll rhs = (ll)bestB * a;
        if (lhs < rhs || (lhs == rhs && a > bestA)) {
          bestA = a;
          bestB = b;
        }
      }
    }

    if (has) cout << "Buy " << bestA << " tickets for $" << bestB << "\n";
    else cout << "No suitable tickets offered\n";
  }

  return 0;
}

이 블로그의 다른 글