Taxol

I’ve always been.

백준 4884 - FIFA 월드컵

Updated:

Java

4884 번 - FIFA 월드컵

문제

FIFA는 월드컵의 대회 형식을 약간 수정하려고 한다. 현재, 월드컵은 32개팀이 참가하며, 2개의 라운드로 이루어져 있다. 첫 번째 라운드는 조별 리그이고, 32개팀은 8개의 조에 배정된다. 각 팀은 조에 속하는 다른 팀과 한 경기씩 치뤄 총 세 경기를 치룬다. 조별 리그가 완료된 후에, 각 조의 상위 두 팀은 다음 라운드 토너먼트로 진출하게 된다. 토너먼트의 첫 번째 라운드는 16개팀이 참가하며, 총 8경기가 열린다. 각 경기의 승자는 다음 라운드에 진출하게 된다. 토너먼트의 두 번째 라운드에서는 총 4경기가 열리며, 각 경기의 승자는 준결승전에 진출한다. 마지막으로 준결승전의 승자 두 팀은 결승전에 진출하게 되고, 결승전의 승자는 월드컵을 우승하게 된다.
토너먼트 전을 공정하게 진행하려면 토너먼트에 참가하는 팀의 수는 항상 2의 제곱꼴이 되어야 한다.
FIFA는 조별 리그에 참가하는 팀의 수를 추가하고, 조의 개수도 추가하려고 한다. 이 결과로 토너먼트에 참가하는 팀의 수가 변경될 수도 있다. 또한, FIFA는 일부 팀(이전 대회 우승, 개최국, 등등…)은 조별 리그를 거치지 않고 바로 토너먼트에 진출하게 규정을 바꾸려고 한다. 월드컵을 어떻게 바꿀지 주어졌을 때, 그렇게 월드컵이 바뀐다면 총 몇 경기가 열리게 되는지 구하는 프로그램을 작성하시오.
문제 출처

접근 방법

문제가 복잡하게 보이지만 수식 2개로 해결되는 문제였다.
이 문제에서 중점으로 봐야 할 내용은

  1. 토너먼트에 진출하는 팀의 수를 2의 N승으로 구하고
  2. 위 토너먼트 진출 수 팀을 이용하여 총 경기 수를 구하는 것이다.

토너먼트에 진출 하는 수는, [그룹의 수 X 각 조에서 토너먼트로 진출하는 팀의 수 + 바로 토너먼트로 진출하는 팀의 수] 이다.
즉 G X A + D를 통하여 구한다.
여기서 문제의 조건에 따라, 2N로 만든다. 두번째 예제 입력의 경우 8*2+1 == 17 이므로, 2N으로 맞추면 토너먼트 수는 32가 되어야 한다.
이후 2번, 총 경기 수 X를 구한다.
이는 [한 조별리그에서 일어나는 총 경기 수 X 그룹의 수 + 토너먼트 이후 일어나는 경기 수]이다.
한 조별리그 경기 수는, 등차수열의 합으로 구할 수 있다.
만약 한 그룹에 4팀이 있다면, 3 + 2 + 1로 총 6경기를 진행하고, 5팀이 있다면 4 + 3 + 2 + 1로 10경기를 진행한다.

그리고 토너먼트 이후 일어나는 경기 수는, 토너먼트 팀 수 - 1이다. 이유는 직접 그려보니 그렇게 나와서 수식을 짰다.
위 두 식으로 주어진 문제를 해결 할 수 있다.

구현

g t a d를 받아 위에서 정리한 수식에 대입한다.
토너먼트에 진출하는 팀의 수를 2N에 맞추는 방법은 while문을 반복하여 수가 2N-1과 2N사이에 들어 왔을 때, 토너먼트의 수를 2N로 대입하는 방식으로 찾았다.
위 과정 수행 중 2N과 처음 토너먼트의 수의 차이가 추가해야할 팀의 수 이므로 이것이 Y가 된다.

여기서 주의해야 할 것이, N이 0에서 부터 시작해야 한다는 것이다.
왜냐하면, 만약 테스트 케이스가 1 1 1 0이면, 토너먼트 수는 1이 되고, 2-1 < 1 <= 20로 통과 할 수 있기때문이다.
N이 1부터 시작하면, 위 조건을 통과하지 못해 무한 루프를 돌게된다.

또한 주의 해야 할 것이, 네 숫자는 최대 216에 근접하다는 것이다.
int형 자료형이 최대 215-1 인데, G*A+D를 하면 216를 넘는 경우가 있기 때문에, 모든 자료형은 long으로 선언해야 오버플로우를 방지 할 수 있다.

내가 이 문제를 풀면서 추가한 테스트 케이스는 다음과 같다.

8 4 2 0
8 4 2 1
9 4 3 1
1 1 1 0
65535 65533 65534 65535
-1 -1 -1 -1
——
이며, 이는 각각
——
8x2/4+0=63+0
8x2/4+1=79+15
1x1/1+0=0+0
9x3/4+1=85+4
65535x65534/65533+65535=140724604076025+131071
——
의 결과가 나온다.

코드

/*
4884번 - FIFA 월드컵
https://www.acmicpc.net/problem/4884
*/
import java.util.*;
import java.io.*;

public class Main {
	static long at = 0;
	static long g,a,t,d;
	static long x,y;
    public static void main(String []args) throws IOException {        
    	System.setIn(new FileInputStream("res/mainInput.txt"));	//제출 할 때 주석해야함
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	while(true) {
    		StringTokenizer stk = new StringTokenizer(br.readLine());
    		g = Integer.parseInt(stk.nextToken()); 
    		t = Integer.parseInt(stk.nextToken());
    		a = Integer.parseInt(stk.nextToken());
    		d = Integer.parseInt(stk.nextToken());
    		if(g == -1) 
    			break;
    		//토너먼트 진출 팀 수 구하기
    		long trmnt = g * a + d; // 그룹 수 x 진출 수 + 바로 진출 수
    		long idx = 0;
    		long chkN1, chkN2;
    		//2의 제곱꼴이 아닐때, 가까운 2의 제곱으로 진출하는 팀의 수를 찾기
    		while(true) {
    			chkN1 = (long) Math.pow(2, idx - 1);
    			chkN2 = (long) Math.pow(2, idx);
    			if(chkN1 < trmnt && trmnt <= chkN2) {
    				y = chkN2 - trmnt;		// 추가해야하는 팀의 수
    				trmnt = chkN2;
    				break;
    			}
    			idx++;
    		}
    		at = (t * (t - 1)) / 2;		// 한 그룹 스테이지에서 팀 토너먼트로 갈때 걸리는 총 경기 수
    		x = at * g + trmnt - 1;		// (at * 그룹 수) + (토너먼트에 진출 후 결승까지 총 경기 수)
    		System.out.println(g + "*" + a + "/"  + t + "+" + d + "=" + x + "+" + y);
    		at = 0;
    	}
    	br.close();
    }
}

총평

난이도

⭐⭐⭐⭐★

후기

복잡하기도 복잡한 문제였지만, 신경써야할 것이 많아 고생했던 문제이다.
int형은 2의 16승 까지인 것을 놓친 것과 시간 초과가 단순히 값이 커서 발생하였다는 생각으로 생각을 많이 한 문제이다.
또한 등차 수열의 합이란 공식을 모르고, 조합으로 문제를 해결 하려한 것도 아쉬웠던 부분 중 하나이다.
수학을 잘해야 한다는 것이 복잡한 공식을 잘해야 하는 것이 아닌, 이 문제 처럼 중/고등학생때 충분히 다루었던 내용을 떠올리는 것이라는 것을 깨달았다.

개선할 점

없

You may also enjoy