[BOJ/백준] 4884번 : FIFA 월드컵 (Java)
📘 백준 4884번 : FIFA 월드컵
💡 문제 풀이
조별 리그에서 토너먼트로 진출한 팀의 수 (qualify) = (그룹의 수 (G) * 각 조에서 토너먼트로 진출하는 팀의 수(A)) + 토너먼트 직행 팀 수(D)
토너먼트 진행 팀 수 (tournament) = qualify보다 처음으로 큰 2의 제곱수
= 2 ^ (log2(qualify)의 올림)
= 2 ^ ((log10(qualify)/log10(2))의 올림)
토너먼트에 추가되는 팀 수 (additionCnt) = 토너먼트 진행 팀 수 (tournament) - 조별 리그에서 토너먼트로 진출한 팀의 수 (qualify)
총 게임 수 = (조별 리그 게임 수) + (토너먼트 게임 수)
= (한 그룹의 경기 수 * 그룹의 수 (G)) + (토너먼트 진행 팀 수 (tournament) - 1)
= (각 그룹의 팀 수(T) * (T - 1) / 2 * G) + (tournament - 1)
‼️ 주의해야 하는 점
데이터 타입은
long이 적합하다.토너먼트 진행 팀 수를 반복문으로 구하면 높은 확률로 시간초과가 난다. (반복문을 어떻게 짜느냐에 따라 다름)
✅ 코드 (Java)
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// https://www.acmicpc.net/problem/4884
// 조별 리그에서 토너먼트로 진출한 팀의 수 (qualify) = G * A + D
// 토너먼트 진행 팀 수 (tournament) = 2^(log2(qualify)의 올림)
// 토너먼트에 추가되는 팀 수 (additionCnt) = tournament - qualify
// 조별 리그 게임 수 = T * (T - 1) / 2 * G
// 토너먼트 게임 수 = tournament - 1
public class B4884_FIFA_월드컵 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String s = "";
while (!(s = br.readLine()).equals("-1 -1 -1 -1")) { // EOI
StringTokenizer st = new StringTokenizer(s);
long G = Long.parseLong(st.nextToken()); // 그룹의 수
long T = Long.parseLong(st.nextToken()); // 각 그룹의 팀 수
long A = Long.parseLong(st.nextToken()); // 각 조에서 토너먼트로 진출하는 팀 수
long D = Long.parseLong(st.nextToken()); // 토너먼트 직행 팀 수
sb.append(G + "*" + A + "/" + T + "+" + D + "="); // 출력 형식 맞추기
long qualify = G * A + D; // 조별 리그에서 토너먼트로 진출한 팀의 수
long tournament = (long) Math.pow(2, (int) Math.ceil(Math.log10(qualify) / Math.log10(2))); // 토너먼트를 진행하는 팀
// 수
long additionCnt = tournament - qualify; // 토너먼트에 추가되는 팀 수
long gameCnt = (T * (T - 1) / 2 * G) + (tournament - 1); // 총 게임 수
sb.append(gameCnt + "+" + additionCnt + "\n"); // 출력 저장
}
System.out.println(sb); // 출력
br.close();
}
}
💾 제출 결과
🧩 새롭게 알게 된 점
Java에서 logab는 Math.log10(b) / Math.log10(a)나 Math.log(b) / Math.log(a)로 구할 수 있다.