Post

[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)

‼️ 주의해야 하는 점

  1. 데이터 타입은 long이 적합하다.

  2. 토너먼트 진행 팀 수를 반복문으로 구하면 높은 확률로 시간초과가 난다. (반복문을 어떻게 짜느냐에 따라 다름)


✅ 코드 (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에서 logabMath.log10(b) / Math.log10(a)Math.log(b) / Math.log(a)로 구할 수 있다.


🔗 참고한 자료