BOJ 9070 - 장보기

문제

BOJ 9070 - 장보기

여러 가게에서 같은 물건을 팔고 있을 때, 단위 가격이 가장 저렴한 가게를 찾는 문제다. 각 가게는 수량 a와 가격 b를 제시하며, 단위 가격(b/a)이 가장 낮은 가게를 선택해 그 가게의 가격 b를 출력한다. 단, 단위 가격이 같다면 수량이 적은 가게(더 적게 사도 되는 가게)를 선택한다.

입력

• 첫째 줄: 테스트 케이스 수 T
• 각 테스트 케이스:
  • 첫째 줄: 가게 수 N
  • 다음 N줄: 각 가게의 수량 a와 가격 b

출력

각 테스트 케이스마다 최선의 가게에서 지불해야 하는 가격 b를 출력한다.

예제

풀이

부동소수점 비교 오류를 피하기 위해 b/a를 직접 나누지 않고 교차곱(cross multiplication)으로 비교한다. 현재까지의 최선 가게 (x, y)와 새 가게 (a, b)의 단위 가격을 b*x와 a*y를 비교해 결정한다.

1. 테스트 케이스 수 T를 입력받는다.
2. 각 테스트 케이스에서 최선 가게를 (x=0, y=2e9)(초기값: 단위 가격 무한대)로 초기화한다.
3. N개의 가게 (a, b)를 순서대로 읽으며 ChooseA(a, b, x, y) 함수로 비교한다.
4. ChooseA 함수: a/b < x/y 즉 a*y < x*b이면 A가 더 저렴하다. 단위 가격이 같으면(a*y == x*b) 수량이 더 작은 쪽을 선택한다.
5. 현재 가게가 더 유리하면 (x, y) 갱신 후 최종 y를 출력한다.

핵심 아이디어: a/b < x/y를 부동소수점 나눗셈 없이 a*y < x*b로 변환하면 정수 연산만으로 정확한 비교가 가능하다. 오버플로를 방지하기 위해 long long을 사용한다.

코드

#include <iostream>
#define ll long long
using namespace std;
 
bool ChooseA(ll Ax, ll Ay, ll Bx, ll By)
{
  if (Ay * Bx != Ax * By)
    return Ay * Bx < Ax * By;
  return Ay < By;
}
 
int main(void)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll T, N, i, a, b;
 
  cin >> T;
  while (T--)
  {
    cin >> N;
 
    ll x = 0, y = 2e9;
    for (i = 1; i <= N; i++)
    {
      cin >> a >> b;
      if (ChooseA(a, b, x, y))
        x = a, y = b;
    }
 
    cout << y << "\n";
  }
}

복잡도

• 시간: O(N) — N개의 가게를 한 번 순회 (총 모든 테스트 케이스의 가게 수 합산)
• 공간: O(1) — 현재 최선 가게 정보만 유지