[ 백준 15953 ] 상금헌터 (C++)
백준의 상금헌터(15953) 문제이다.
[ 문제풀이 ]
제이지가 1회 코드 페스티벌에서 a등, 2회 코드 페스티벌에서 b등을 했을 때, 얻을 수 있는 총 상금이 얼마인지를 구해야 하는 문제이다.
#1. 등수에 따른 순위 구하기
본인은 가장 먼저, '등수'에 따른 '순위'를 구해놓았다. 등수와 순위가 같은 말이라서 무슨 말인지 모르겠지만 지금부터 알아보자..
1회 코드 페스티벌을 보게 되면, 1등은 1명, 2등은 2명, 3등은 3명... 이런식으로 순위가 매겨지게 된다.
그럼, 제이지가 전체에서 6명 안에 들었다면 몇 등이 되는 것일까 ??
1명 안에 들었다면 1등이 될 것이고
3명 안에 들었다면 2등이 될 것이다.
6명 안에 들었다면 3등이 될 것이다. 즉, 제이지가 6등을 하게되면 이는 순위표에 따르면 '3순위'가 된다는 것이다.
그래서, 이런식으로 등수에 따른 순위를 모두 구해놓고 시작하였다.
이를 위해 수식을 하나 사용해 주었다.
Festival[A(0 / 1)][B] 라는 수식을 사용해 주었는데,
Festival[0][A] = C : 제 1회 코드페스티벌에서 C등을 했을 경우, 그 순위는 A순위입니다.
Festival[1][A] = C : 제 2회 코드페스티벌에서 C등을 했을 경우, 그 순위는 A순위입니다.
를 의미한다. 이 값들을 구하는 부분을 코드로 나타내면 다음과 같다.
void Setting()
{
for (int i = 1; i <= 6; i++) Festival[0][i] += Festival[0][i - 1] + i;
for (int i = 1, A = 1; i <= 5; i++, A *= 2) Festival[1][i] += Festival[1][i - 1] + A;
}위의 코드를 실행시키게 되면 Festival[][] 변수에는 다음과 같은 결과값들이 저장될 것이다.
Festival[0][1] = 1; Festival[0][2] = 3; Festival[0][3] = 6 ....
Festival[1][1] = 1; Festival[1][2] = 3; Festival[1][3] = 7; Festival[1][4] = 15...
#2. 정답 도출
이제 #1에서 구해놓은 등수에 따른 순위를 구해서 상금만 더해주면 된다.
그럼, 제 1회 코드페스티벌에서 5등을 했다고 가정을 해보자. 이를 순위로 나타내면 몇 순위가 될까 ???
#1에서 구해놓은 Festival에 의하면 Festival[0][2] = 3, Festival[0][3] = 6이 될 것이다.
5등이라는 값은 Festival[0][2] 와 [0][3] 사이에 있는 값이 된다. 즉 ! 이 경우에는 '3순위'를 하게 됨을 의미한다.
즉, X등을 했을 때, 이 X라는 값이 Festival[0][K] 와 [0][K + 1] 사이에 있다면, 이 경우에는 K + 1순위를 하게 된다는 것을 의미한다. 이렇게 순위를 구한 후, 순위에 따른 상금을 구해주면 정답을 도출할 수 있다.
[ 소스코드 ]
|
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include <iostream>
#include <vector>
using namespace std;
int T;
vector<pair<int, int>> V;
int Festival[2][7];
void Input()
{
cin >> T;
for (int i = 0; i < T; i++)
{
int a, b; cin >> a >> b;
V.push_back(make_pair(a, b));
}
}
void Setting()
{
for (int i = 1; i <= 6; i++) Festival[0][i] += Festival[0][i - 1] + i;
for (int i = 1, A = 1; i <= 5; i++, A *= 2) Festival[1][i] += Festival[1][i - 1] + A;
}
int Find_Ranking(int Rank, int Idx)
{
if (Rank == 0) return 0;
if (Rank == 1) return 1;
for (int i = 1; i < 6 - Idx; i++)
{
if (Festival[Idx][i] <= Rank && Rank <= Festival[Idx][i + 1]) return i + 1;
}
return 0;
}
int Find_Money(int Rank, int Idx)
{
if (Rank == 0) return 0;
if (Idx == 0)
{
if (Rank == 1) return 5000000;
if (Rank == 2) return 3000000;
if (Rank == 3) return 2000000;
if (Rank == 4) return 500000;
if (Rank == 5) return 300000;
if (Rank == 6) return 100000;
}
else
{
if (Rank == 1) return 5120000;
if (Rank == 2) return 2560000;
if (Rank == 3) return 1280000;
if (Rank == 4) return 640000;
if (Rank == 5) return 320000;
}
}
void Calculate()
{
for (int i = 0; i < T; i++)
{
int A = V[i].first;
int B = V[i].second;
int Ranking1 = Find_Ranking(A, 0);
int Prize1 = Find_Money(Ranking1, 0);
int Ranking2 = Find_Ranking(B, 1);
int Prize2 = Find_Money(Ranking2, 1);
cout << Prize1 + Prize2 << endl;
}
}
void Solution()
{
Setting();
Calculate();
}
void Solve()
{
Input();
Solution();
}
int main(void)
{
//freopen("Input.txt", "r", stdin);
Solve();
return 0;
}
|
cs |