문제
두 대회에서 각각의 등수가 주어질 때, 받을 수 있는 총 상금을 구하라. 각 대회는 등수 구간별로 다른 상금이 배정된다.
입력
테스트 케이스 수 T, 각 케이스마다 두 대회의 등수가 주어진다 (0이면 참가하지 않음).
출력
각 케이스마다 총 상금을 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 1 1 | 10120000 |
풀이
상금 테이블과 인원 배분을 미리 정의하고 등수 구간을 판별한다.
- 첫 번째 대회: 인원
{1, 2, 3, 4, 5, 6}명씩 상금{500, 300, 200, 50, 30, 10}만원 - 두 번째 대회: 인원
{1, 2, 4, 8, 16}명씩 상금{512, 256, 128, 64, 32}만원 - 등수에서 각 구간의 인원을 차감하며 해당 구간을 찾는다
- 두 대회의 상금을 합산하고 10000을 곱한다
핵심 아이디어: 등수에서 각 구간 인원을 순차적으로 빼면, 0 이하가 되는 시점의 구간이 해당 등수의 상금 구간이다.
코드
#include <bits/stdc++.h>
using namespace std;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int prize1[6] = {500, 300, 200, 50, 30, 10};
int prize2[5] = {512, 256, 128, 64, 32};
int t;
cin >> t;
while (t--)
{
int a, b, sum = 0;
cin >> a >> b;
if (a)
{
for (int i = 0; i < 6; i++)
{
a -= i + 1;
if (a <= 0)
{
sum += prize1[i];
break;
};
}
}
if (b)
{
for (int i = 0; i < 5; i++)
{
b -= (1 << i);
if (b <= 0)
{
sum += prize2[i];
break;
}
}
}
cout << sum * 10000 << '\n';
}
}복잡도
- 시간: O(T) (T: 테스트 케이스 수, 내부 반복은 상수)
- 공간: O(1)