문제 출처 : https://www.acmicpc.net/problem/9547
9547번: 대통령 선거
문제 대선이 끝난 후 2주가 지났으나 여전히 결과는 발표되지 않았다. 결과가 궁금한 성제는 결과를 직접 미리 알아보기로 했다. 성제는 모종의 방법으로 투표에 참여한 모든 사람들에 대해 한 명도 빠짐없이 선호도 조사를 마쳤다. 성제는 투표에 참여한 사람들이 항상 선호도에 따라 투표했음을 알고 있다. 예를 들어 대통령 후보가 5명이고 어떤 유권자의 선호도가 [3, 2, 5, 1, 4] 인 상태에서 2번 후보와 4번 후보가 경합을 벌인다면, 이 유권자는 2번
www.acmicpc.net
이 문제는 문제를 이해하느라 많은 시간과 횟수를 소모한 문제이다.
대통령 선거를 할 때 첫 번째 경우와 두 번째 경우로 나뉘게 되는데
첫 번째 경우에는 한 후보가 과반수 이상의 투표를 받게 되면 당선이 되는 것이고
두 번째 경우에는 그렇지 않은 경우 가장 많은 표를 받은 두 사람이 투표를 다시 하게 되는 방식인데
유권자의 투표는 그대로 돌아가게 된다.
그러므로 그 두 후보한테 가는 표만이 유효표이고 선호도에 따라 투표가 진행된다.
아래는 해당 문제를 해결한 소스이다.
|
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
|
#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
//freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
int Test;
int num;
scanf("%d", &Test);
for (int i = 0; i < Test; i++)
{
int visit[101] = { 0, };
int max_index = 0;
int max = 0;
int second = 0;
int second_index = 0;
int arr[101][101] = { 0, };
int check[101] = { 0, };
int C;
int V;
scanf("%d %d", &C, &V);
for (int j = 0; j < V; j++)
{
for (int k = 0; k < C; k++)
scanf("%d", &arr[j][k]);
}
for (int j = 0; j < V; j++)
{
if (arr[j][0] != 0)
check[arr[j][0]]++;
}
for (int j = 0; j <=C; j++)
{
if (check[j] > max)
{
max = check[j];
max_index = j;
}
}
for (int j = 0; j <= C; j++)
{
if (check[j] > second && second <= max && max_index!=j)
{
second = check[j];
second_index = j;
}
}
if (max >= (double)V / 2)
printf("%d %d\n", max_index , 1);
else
{
for (int j = 1; j < C; j++)
{
for (int k = 0; k < V; k++)
{
if (arr[k][0] != max_index && arr[k][0] != second_index && visit[k]==0)
{
if (arr[k][j] == max_index)
{
max++;
visit[k]++;
}
else if (arr[k][j] == second_index)
{
second++;
visit[k]++;
}
}
}
}
if (max >= (double)V / 2)
printf("%d %d\n", max_index, 2);
else if (second >= (double)V / 2)
printf("%d %d\n", second_index, 2);
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
'알고리즘' 카테고리의 다른 글
| 백준 18111번 문제 ( 마인크래프트 ) (0) | 2020.02.01 |
|---|---|
| 백준 2504번 문제 ( 괄호의 값 ) (0) | 2020.02.01 |
| 백준 10819번 문제 ( 차이를 최대로 ) (0) | 2020.01.09 |
| 백준 14889번 문제 ( 스타트와 링크 ) (0) | 2020.01.09 |
| 백준 17521번 문제 ( Byte Coin ) (0) | 2020.01.08 |
뀨심볼
깃허브 주소는 : https://github.com/hhyc2 입니다~