월드컵

문제

문제 설명

월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.

네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.

제한 사항

첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다. 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0이다.

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

입출력 예

입력	출력
5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4	1 1 0 0

입출력 예 설명

혼자 두 번 비길 수 없어서 실패

승리는 13번 했는데 패배를 14번 해서 불가

아이디어 (실패)

1. 승리 횟수와 패배 횟수가 동일할 것

   

2. 무승부 개수 = (총 게임 - 승리 횟수) * 2

   예를 들어 15 게임 중에 13번만 승리했다면 2번의 무승부:무승부 가 발생했기에 총 무승부가 네 번 기록된다

   4 = (15 - 13) * 2

   

3. 모든 나라는 승 + 무 + 패 다 합치면 5여야 함

4. 만약 누가 5번 이겼다면, 모든 나라는 한 번씩 패배 기록이 있어야 함

5. 만약 누가 5번 졌다면, 모든 나라는 한 번씩 승리 기록이 있어야 함

제출 코드 (실패)

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
 @author ranuinclulus
 @since 2024.08.22
 @link https://www.acmicpc.net/problem/6987
 @timecomplex
 @performance
 @category
 @note
 */
public class Main {
    class Contury {
        int win;
        int loss;
        int draw;
        int game;

        public Contury(int win, int draw, int loss) {
            this.win = win;
            this.draw = draw;
            this.loss = loss;
            this.game = win + loss + draw;
        }

        @Override
        public String toString() {
            return "Contury{" +
                    "win=" + win +
                    ", loss=" + loss +
                    ", draw=" + draw +
                    ", game=" + game +
                    '}';
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static boolean possible;
    static Contury[] conturies;

    // 총 15번의 경기
    public void solution() throws IOException {
        for (int i = 0; i < 4; i++) {
            possible = true;
            conturies = new Contury[6];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 6; j++) {
                conturies[j] = new Contury(
                        Integer.parseInt(st.nextToken()),
                        Integer.parseInt(st.nextToken()),
                        Integer.parseInt(st.nextToken())
                );
            }
            int totalWin = 0;
            int totalLoss = 0;
            int totalDraw = 0;
            int drawCnt = 0;
            int allWin = - 1;
            int allLoss = -1;
            int allDraw = -1;

            for (int j = 0; j < 6; j++) {
                Contury c = conturies[j];
                totalWin += c.win;
                totalLoss += c.loss;
                totalDraw += c.draw;

                if (c.game != 5) possible = false;
                if (c.draw != 0) drawCnt++;

                if (c.win == 5) allWin = j;
                if (c.loss == 5) allLoss = j;
                if (c.draw == 5) allDraw = j;
            }

            if (totalWin != totalLoss)  possible = false;
            if (totalWin == totalLoss && (15 - totalWin) * 2 != totalDraw)  possible = false;
            if (drawCnt == 1)  possible = false;

            if (allWin != -1) {
                for (int j = 0; j < 6; j++) {
                    if (j == allWin) continue;
                    if (conturies[j].loss < 1) possible = false;
                }
            }

            if (allLoss != -1) {
                for (int j = 0; j < 6; j++) {
                    if (j == allLoss) continue;
                    if (conturies[j].win < 1) possible = false;
                }
            }

            if (allDraw != -1) {
                for (int j = 0; j < 6; j++) {
                    if (j == allDraw) continue;
                    if (conturies[j].draw < 1) possible = false;
                }
            }
            sb.append(possible ? 1 : 0).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

아주아주 길고 코드가 더러워짐

카운트하는 변수가 너무 많아져서 헷갈리기 시작..

누가 뭘 카운트하는지 까먹고 이게 맞나 싶어짐

심지어 맞지도 않음

예외를 내가 다 컨트롤할 수 없을 거라 판단 → 다른 아이디어 접근

아이디어 (재시도)

• 얘네는 6명의 도시들이 각각 5번씩 게임하기 때문에 총 게임 횟수가 15개의 조합으로 나오므로 수가 아주 적음
• {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {1, 2}, {1, 3}, {1, 4}, {1, 5} … 등으로 대진표를 만들어 둔 뒤 총 15번의 게임을 다 돌 수 있는 결과표면 성공, 아니면 불가능으로 판별해 보자

제출 코드 (성공)

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/*
 @author ranuinclulus
 @since 2024.08.22
 @link https://www.acmicpc.net/problem/6987
 @timecomplex
 @performance
 @category
 @note
 */
public class Main {
    class Country {
        int win;
        int loss;
        int draw;
        int game;

        public Country(int win, int draw, int loss) {
            this.win = win;
            this.draw = draw;
            this.loss = loss;
            this.game = win + loss + draw;
        }

    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static boolean possible;
    static Country[] countries;
    static int[][] combination = new int[][] {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5},
            {1, 2}, {1, 3}, {1, 4}, {1, 5},
            {2, 3}, {2, 4}, {2, 5},
            {3, 4}, {3, 5},
            {4, 5}};

    // 총 15번의 경기
    public void solution() throws IOException {
        for (int i = 0; i < 4; i++) {
            possible = false;
            countries = new Country[6];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 6; j++) {
                countries[j] = new Country(
                        Integer.parseInt(st.nextToken()),
                        Integer.parseInt(st.nextToken()),
                        Integer.parseInt(st.nextToken())
                );
            }

            game(0);
            
            for (Country c : countries) {
                if (c.game != 5) possible = false;
            }
            sb.append(possible ? 1 : 0).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private void game(int depth) {
        if (depth == 15) {
            possible = true;
            return;
        }

        Country team1 = countries[combination[depth][0]];
        Country team2 = countries[combination[depth][1]];

        if (team1.win > 0 && team2.loss > 0) {
            team1.win--;
            team2.loss--;
            game(depth + 1);
            team1.win++;
            team2.loss++;
        }

        if (team1.draw > 0 & team2.draw > 0) {
            team1.draw--;
            team2.draw--;
            game(depth + 1);
            team1.draw++;
            team2.draw++;
        }

        if (team1.loss > 0 && team2.win > 0) {
            team1.loss--;
            team2.win--;
            game(depth + 1);
            team1.loss++;
            team2.win++;
        }
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

도시 객체 생성

• 승, 무, 패를 기록
• 생성자를 통해 승, 무, 패가 입력된 순간 한 도시가 게임한 횟수 자동으로 계산

1 ~ 6번 도시끼리의 대진표 작성

• 무식하게 썼음
• List<int[]>를 만들어서 생성되는 조합을 List에 넣고 관리하기도 했는데, 도시 개수가 아주 작은 수로 정해져 있어서인지 하드로 코딩했을 때 시간이랑 메모리 절약
• 만약 도시 개수가 변수로 주어진다면 직접 조합 구할 필요 있음
• List가 무거우면 비트 마스킹으로 구했어도 될 것 같았다… 라는 생각이 발표를 준비하는 현재 떠오름

재귀문 종료 조건과 대진 시작

• 게임을 무사히 15번 하면 성공한 결과표이므로 종료
• 내가 만든 대진표에서 depth 번째 참가하는 도시들의 참여 목록을 꺼내 옴

1이 이기고 2가 졌을 때

둘 다 비겼을 때

1이 지고 2가 이겼을 때

마지막으로 도시들 중에 게임을 다섯 번 하지 않은 애가 있는지 검사

깨달은 점

• 처음에 여기 부분에서 Country tean1 = 하고 꺼내지 않고 그대로 써서 countries[combination][depth][0].draw 이렇게 쓰다가 내 코드를 못 읽었다
• 메모리나 시간도 중요하지만 가독성도 중요한 것 같다… 라고 나름 생각
• 특히 이번 코드는 Country로 객체를 만든 게 많이 도움이 됐다