문제
BOJ 4289 - Rock-Paper-Scissors Tournament
N명의 참가자가 라운드 로빈 방식의 가위바위보 토너먼트에 참여한다. 각 쌍이 K번씩 대결하며, 각 대결 결과(선수 번호와 선택한 가위/바위/보)가 주어진다. 각 선수의 승률(이긴 횟수 / 비기지 않은 횟수)을 소수점 3자리까지 출력하고, 비기지 않은 대결이 없으면 -를 출력한다.
입력
- 입력은 여러 테스트 케이스로 구성되며,
0이 입력되면 종료한다. - 각 테스트 케이스:
- N K (참가자 수, 쌍당 대결 수)
- 이후 K × N(N-1)/2개의 대결 결과:
x hand1 y hand2형식 (hand는rock,scissors,paper중 하나)
출력
각 테스트 케이스마다 N명의 승률을 한 줄씩 출력하고, 케이스 사이에 빈 줄을 출력한다. 비기지 않은 대결이 없으면 -를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 1 1 rock 2 scissors 0 | 1.000 - |
풀이
모든 대결 결과를 순회하며 각 선수의 승수와 비기지 않은 대결 수를 누적한 뒤, 승률을 계산하여 출력하는 구현 문제이다.
- N과 K를 읽는다. N이 0이면 종료한다.
- 각 선수의 승수 배열
b[]와 비기지 않은 대결 수 배열p[]를 0으로 초기화한다. - K × N(N-1)/2번의 대결 결과를 읽으며:
- 가위바위보 승패 규칙(rock vs scissors, scissors vs paper, paper vs rock)에 따라 이긴 선수의
b[]를 증가시킨다. - 두 선수의 선택이 다르면(비기지 않으면) 양쪽의
p[]를 증가시킨다.
- 가위바위보 승패 규칙(rock vs scissors, scissors vs paper, paper vs rock)에 따라 이긴 선수의
- 각 선수에 대해
p[i] == 0이면-, 아니면b[i] / p[i]를 소수점 3자리로 출력한다.
핵심 아이디어: 비기지 않은 대결 수(p[])를 분모로 사용하여 승률을 계산한다. 두 손 모양의 첫 글자만 비교하면 6가지 승패 조건을 간결하게 처리할 수 있다. 부동소수점 반올림을 위해 +0.000000005를 더해 출력한다.
코드
#include<iostream>
using namespace std;
int b[200],p[200];
char b1[20], b2[20];
int main() {
int n, k, i;
while (1) {
scanf("%d", &n);
if (n == 0) break;
scanf("%d", &k);
for (i = 1; i <= n; i++) { b[i] = 0; p[i] = 0; }
for (i = 1; i <= k * n * (n - 1) / 2; i++) {
int x, y;
scanf("%d %s %d %s", &x, b1, &y, b2);
if (b1[0] == 'r' && b2[0] == 's') b[x]++;
if (b1[0] == 's' && b2[0] == 'p') b[x]++;
if (b1[0] == 'p' && b2[0] == 'r') b[x]++;
if (b2[0] == 'r' && b1[0] == 's') b[y]++;
if (b2[0] == 's' && b1[0] == 'p') b[y]++;
if (b2[0] == 'p' && b1[0] == 'r') b[y]++;
if (b1[0] != b2[0]) { p[x]++; p[y]++; }
}
for (i = 1; i <= n; i++) {
if (p[i] == 0) printf("-\n");
else printf("%.3lf\n", (double)(b[i]) / p[i]+0.000000005);
}
printf("\n");
}
return 0;
}복잡도
- 시간: O(K × N²) — 전체 대결 수 K × N(N-1)/2만큼 반복
- 공간: O(N) — 선수 수만큼의 승수 및 대결 수 배열