cdjs의 코딩 공부방

https://acmicpc.net/problem/3031

* 혹시라도 맞왜틀??? 을 외치며 블로그에 들어오신 분이라면 "여담" 부분에 몇 가지 예외 케이스를 작성했으니 확인해 보시기 바랍니다.

1. 문제

- $N$개의 팀의 경기 수 / 이긴 횟수 / 비긴 횟수 / 진 횟수 / 승점이 주어진다. 이 때, ?로 주어지면 해당 부분은 알려지지 않았다는 의미이다.

- 승리 시에 팀은 3점, 비긴 시에 팀은 1점의 승점을 획득한다.

- 각 팀의 ?로 되어 있는 부분이 무엇인지 유추하여라.

- 각 팀의 최대 경기 수는 100회이며, 빈 칸을 채우는 경우가 유일한 경우만 주어지는 것이 보장된다.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

처음 이 문제를 보자마자 든 생각은 "개쉬운데?" 였다.

사실 그도 그럴것이, 처음에는 케이스가 그렇게 많이 나뉠줄 몰랐기 때문이다.

사실 이 문제는 케이스를 잘 나눠서 어떻게든 ?를 채우기만 하면 되기 때문에, 문제 관찰 과정이랄게 딱히 없으니 케이스를 나누며 문제를 풀어 보자.

우선, 기본 조건을 먼저 생각해 보자.

"각 팀은 최대 100경기를 소화했다" 라는 것은, 승 / 무 / 패 의 합이 최대 100이라는 뜻이다.

따라서, 문제를 풀기 이전에 먼저 승 / 무 / 패 중 하나 혹은 두개의 합이 100이라면, 다른 승 / 무 / 패 중 주어지지 않은 것이 있더라도 0으로 바꿔줄 수 있다.

또한, 총 경기 수가 이미 주어진 경우에 한해서, 위와 동일하게 승 / 무 / 패 중 하나 혹은 두개의 합이 총 경기 수와 동일하다면, 다른 승 / 무 / 패 중 주어지지 않은 것이 있더라도 0으로 바꿔줄 수 있다.

(TMI - 원래 풀이 과정에서는 가장 늦게 생각나버려서 시간 소진을 많이 하게 된 부분이지만, 풀이 과정 설명을 위해선 위쪽에 서술해야 하므로 어쩔 수 없이 여기에 작성하였다.)

이제 케이스를 나눠 보자.

케이스를 어떻게 나눠야 할지는 사람마다 생각이 다를 수 있겠지만, 나는 총 경기 수와 승점 두 부분의 케이스를 먼저 나눠 주었다.

- 총 경기 수와 승점 둘 모두 주어지지 않은 경우

이 경우, 승/무/패 모두 알려져 있어야 한다. 셋 중 하나라도 모르는 경우에는 승점과 경기 수 모두 구할 수 없기 때문이다.

- 총 경기 수가 알려져 있지 않지만 승점이 알려져 있는 경우

이 경우 주의해야 하는 점은 총 승점에 의해 승/무/패 횟수가 고정되는 경우가 있을 수 있다는 것이다.

가령, 총 승점이 298점인 경우를 상정해 보자.

최대 경기 횟수가 100회이기 때문에, 이 경우는 100 99 1 0 298 만으로 주어질 수 있다.

따라서, 총 경기 횟수 / 승 / 무 / 패 모두 알려져 있지 않고 총 승점만 알려져 있는 경우에도 정답이 도출될 수 있다.

이 점에 유의하여 승점에 따라 승 / 무 / 패 횟수를 선택하면 된다.

이 때, 반드시 방법이 유일한 경우만 제시된다고 하였으므로 이미 주어진 것이 무엇인지만 잘 고려하면서 대충 때려박으면 된다.

- 총 경기 수가 알려져 있지만 승점이 알려져 있지 않은 경우

승점이 알려져 있지 않다는 것은, 승 / 무 / 패의 횟수가 총 경기 수에 의해서만 결정되므로 셋 중 두개 이상은 반드시 알려져 있다.

따라서 그냥 하나씩 확인해보면서 승 / 무 / 패 횟수를 정하고, 총 승점도 그에 따라 결정해 주면 된다.

- 총 경기 수와 승점이 모두 알려져 있는 경우

총 경기 수와 승점이 모두 알려져 있다면, 승 / 무 / 패 횟수를 간단히 구할 수 있다.

이미 무승부 횟수가 정해져 있다면 승리 횟수를, 이미 승리 횟수가 정해져 있다면 무승부 횟수를 쉽게 구할 수 있다.

만약 무승부 / 승리 횟수 모두 정해져 있지 않았다면 패배 횟수가 주어졌는지 여부로 판단해야 한다.

패배 횟수가 정해져 있다면 승점과 경기 수에 의하여 승 / 패 횟수가 정해질 수 있기 때문이다.

가령 7 ? ? 1 6으로 정보가 주어진다면, 승리 1회 / 무승부 3회 또는 승리 2회 / 무승부 0회는 불가능하며 오직 승리 0회 / 무승부 6회만 가능하기 때문이다.

그러나 패배 횟수가 정해져 있지 않다면 빈칸을 채우는 방법이 유일한 경우만 주어진다는 제한 조건에 의하여 그런 제한 조건을 생각하지 않고 단순히 승 횟수를 승점 / 3, 무승부 횟수를 승점 - (승리 횟수 * 3)으로 구할 수 있다.

이 때의 패배 횟수는 총 경기 수 - 승리 횟수 - 무승부 횟수 로 구할 수 있을 것이다

모든 케이스를 나눴으므로, 이제 이를 직접 구현해 보자.

4. 코드

(코드가 많이 더럽다... ㅠㅠ)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n;
    int games, win, lose, draw, points;
    string a, b, c, d, e;
    cin >> n;
    for (int i=0; i<n; i++) {
        games = win = lose = draw = points = -1;
        cin >> a >> b >> c >> d >> e;
        if (a!="?") games = stoi(a);
        if (b!="?") win = stoi(b);
        if (c!="?") draw = stoi(c);
        if (d!="?") lose = stoi(d);
        if (e!="?") points = stoi(e);

        // 100경기 제한에 의한 win, draw, lose 결정
        if (win == 100) draw = lose = 0;
        if (draw == 100)    win = lose = 0;
        if (lose == 100)    win = draw = 0;
        if (win+draw == 100)    lose = 0;
        if (draw+lose == 100)   win = 0;
        if (win+lose == 100)    draw = 0;

        if (games == 0) win = draw = lose = points = 0;

        if (games == -1) {
            // game을 모를 때
            if (points == -1) {
                // game과 points 모두 모를 때
                points = 3*win + draw;
            }
            else {
                // game은 모르고 points를 알 때
                if (lose == -1) lose = 0;
                if (win == -1 && draw == -1) {
                    // win, draw 모두 알려지지 않았으면 반드시 이렇게 되야 함.
                    win = points / 3;
                    draw = points - (3*win);
                }
                if (win == -1)  win = (points - draw)/3;
                if (draw == -1) draw = points - (3*win);
            }

            games = win + lose + draw;
        }
        else {
            if (win == games) draw = lose = 0;
            if (draw == games)    win = lose = 0;
            if (lose == games)    win = draw = 0;
            if (win+draw == games)    lose = 0;
            if (draw+lose == games)   win = 0;
            if (win+lose == games)    draw = 0;
        }

        if (points == -1) {
            // games는 있고 points는 없는 경우
            if (win == -1)  win = games - draw - lose;
            if (lose == -1) lose = games - win - draw;
            if (draw == -1) draw = games - win - lose;
            points = 3*win + draw;
        }

        // games, points 모두 값이 있을 때
        if (win == -1)  {
            if (draw == -1) win = points / 3;
            else    win = (points - draw) / 3;
        }
        if (draw == -1) draw = points - (3 * win);
        if (lose==-1)   lose = games - win - draw;
        while (win + draw < games - lose) {
            win--;
            draw+=3;
        }
        cout << games << " " << win << " " << draw << " " << lose << " " << points << "\n";
    }
}

5. 여담

정말 정말 쉬워 보이는 문제이지만, 고려해야 하는 부분들이 너무 많아서 그냥 화가 계속 난다.

만약 대회에서 이런 문제가 나왔다?? 진짜 이 문제 하나때문에 대회 망하는 팀이 한둘이 아닐 거라는 생각이 든다..

혹시라도 "맞왜틀??????" 을 외치며 이 블로그에 들어온 사람이 있다면 내가 문제를 풀면서 넣어 봤던 여러 케이스들을 작성해 본다.

정말 풀면서 고통스러웠던 문제...