BOJ 9501 - 꿍의 우주여행

문제

BOJ 9501 - 꿍의 우주여행

꿍은 우주여행 중 여러 별을 방문하려고 한다. 각 별에는 방문 가치(v), 연료 효율(f), 연료 소모량(c)이 주어진다. 꿍은 우주선의 연비 기준 d 이상인 별만 방문할 수 있다. 방문 가능한 별의 수를 구하라.

별의 방문 가능 조건: v * f / c >= d

입력

• 첫 번째 줄에 테스트케이스 수 T가 주어진다.
• 각 테스트케이스의 첫 줄에 별의 수 N과 기준 값 d가 주어진다.
• 다음 N개의 줄에 각 별의 v, f, c가 주어진다.

출력

각 테스트케이스마다 방문 가능한 별의 수를 출력한다.

예제

풀이

각 별의 연비(v * f / c)를 계산하여 기준 d 이상인 별의 수를 세는 단순 구현 문제이다.

1. T개의 테스트케이스를 반복 처리한다.
2. 각 테스트케이스에서 N개의 별 정보(v, f, c)를 입력받는다.
3. v * f / c >= d 조건을 만족하는 별의 수를 카운트한다.
4. 결과를 출력한다.

핵심 아이디어: 정수 나눗셈의 순서에 주의해야 한다. v * f / c는 곱셈을 먼저 수행한 뒤 나눗셈을 해야 올바른 결과가 나온다.

코드

#include <iostream>
 
using namespace std;
 
int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    int n, d, ans = 0;
    cin >> n >> d;
    while (n--)
    {
      int vi, fi, ci;
      cin >> vi >> fi >> ci;
      if (vi * fi / ci >= d)
        ans++;
    }
    cout << ans << '\n';
  }
}

복잡도

• 시간: O(T * N) - 테스트케이스 수 T, 별의 수 N에 비례
• 공간: O(1) - 추가 메모리 불필요