[BOJ 4884] FIFA 월드컵

서론

백준 4884번 FIFA 월드컵은 solved.ac 기준 Bronze 1 문제임에도 불구하고, 정답자가 30%밖에 되지 않습니다. 문제 자체의 난이도는 높지 않으나, 간과하기 쉬운 부분이 있어서 많이 틀리지 않았을까 생각합니다.

4884번: FIFA 월드컵

 

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

입력
입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 자연수 4개 G T A D가 주어진다.
G > 0는 그룹의 수, T는 각 그룹을 구성하는 팀의 수, A는 각 조에서 토너먼트로 진출하는 팀의 수, D는 조별 리그를 거치지 않고 바로 토너먼트로 진출하는 팀의 수이다. 항상 0 < A ≤ T이고, 네 숫자는 2^16을 넘지 않는다.
만약, 토너먼트에 참가하는 팀의 수가 2의 제곱꼴이 아닐 때는, 가까운 2의 제곱으로 진출하는 팀의 수를 추가시켜야 한다.
입력의 마지막 줄에는 -1이 네 개 주어진다.

출력

각 테스트 케이스에 대해서, 다음을 출력한다.

G*A/T+D=X+Y

G, A, T, D는 입력으로 주어지는 수, X는 총 열리는 경기의 수, Y는 추가해야하는 팀의 수이다.

 

8byte 정수타입을 변수에 사용하자!

G,T,A,D의 변수를 long으로 두는 것 외에도, 중간 계산 과정의 모든 변수를 long으로 두어야 합니다.

그룹스테이지 게임과 토너먼트 게임을 계산하는 과정에서도 2^16 이상의 값을 처리하여야 하기 때문입니다. 아래에서 설명하겠지만, 가장 큰 경우는 (2^31-2^30)*2^30 > 2^61의 경우가 나오기 때문에 int형을 사용하셨다면 오버플로우가 발생하여 while문에 작성한 조건에 따라 무한루프를 돌아 시간초과가 발생할 수 있습니다.

그룹 스테이지와 토너먼트 게임의 이해

월드컵은 Group Stage와 Knockout Tournament로 나뉩니다. Group Stage는 리그전 방식으로 치러지는데, 이는 자기 팀을 제외한 같은 조의 다른 모든 팀과 1판씩 경기하는 것을 의미합니다. Tournament는 두 팀이 붙어서 승자가 다음 라운드에 진출하고 패자는 탈락하는 경기 방식입니다. Group Stage를 살펴보면, 4개 팀의 경우엔 (1vs2+1vs3+1vs4)+(2vs3+2vs4)+(3vs4) => 3+2+1 = 6경기입니다. 1에서부터 (Group Stage 팀 갯수 - 1)의 합을 구하고 이는 첫항이 1이고 등차가 1인 등차수열의 합, ((T-1)*T/2)*G로 계산합니다. Tournament의 경우에는, 8팀이 경기할 경우 4(8강전) + 2(4강전) + 1(결승) = 7경기이고, 16팀의 경우에는 8+4+2+1=15경기 입니다. 등비급수의 합 공식을 사용해도 되지만, 종이로 여러 케이스를 직접 적으시다 보면 (Tournament 진출 팀의 갯수) - 1이란 규칙을 눈으로 찾을 수도 있습니다.

보충자료 : engineershelp.tistory.com/403

부전승과 토너먼트 팀 갯수

문제에서 Tournament 경기를 치르는 팀의 갯수는 항상 2^n (n은 자연수)가 되어야 하며, 만약 이 조건을 충족하지 못하면 Y개 팀을 추가하여 2^n꼴로 만들어 주어야 합니다. Tournament 진출하는 팀은 Group Stage에서 G개 조의 상위 A개 팀(G*A), 부전승으로 Tournament에 진출한 D개 팀입니다. G*A+D는 2^n임을 보장할 수 없기에 문제에 명시된 'Y개 팀을 추가하는 로직'까지 구현하셔야 합니다.

int i = 0;
while(true) {
    if((long)Math.pow(2, i) <= tnmt_teams && 
        tnmt_teams < (long)Math.pow(2, i+1) ) {
        break;
    }
    i++;
}
long p1 = (long)Math.pow(2, i);
long p2 = (long)Math.pow(2, i+1);
if (tnmt_teams != p1) {
    {
        add_teams = p2 - tnmt_teams;
        tnmt_teams = p2;
    }
}

 

문제의 의의?

프로그래밍을 처음 공부하실 때 data type에 대한 공부는 소홀히 하기 쉽습니다. 작은 것과 큰 것 정도는 알지만 구체적인 범위까지 제대로 공부하시는 분은 드문 것 같습니다. 그러나 data type의 범위를 착각해 생기는 버그는 쉽게 찾기 힘듭니다. 연구실 인턴을 하면서 제가 짠 코드가 오작동하였지만 3주 동안 문제를 해결하지 못했는데, 원인은 C에서 강제로 explicit type casting을 잘못 사용하는 바람에 변수의 데이터가 type casting 도중 일정 부분 손실되기 때문이었습니다. 논리적으로 잘못된 explicit type casting 사용은 컴파일러에서 오류를 출력하지 않기 때문에 디버그가 어려워집니다. 올바른 data type 사용과 적절한 type casting은 중요한 문제이며, 이 문제를 풀면서 중요성을 다시 느낄 수 있었습니다.

컴퓨터공학 전공자라면 System Programming 혹은 Digital Logic 과목에서, 비전공자 분들은 프린스턴 대학의 자바 교재(영어)에서 배울 수 있습니다.