백준 14717번 앉았다 :: 마이구미

이 글은 백준 알고리즘 문제 14717번 "앉았다" 를 풀이한다.

수학 과정 중 "조합" 을 활용하여 문제를 해결할 수 있다.

최근 충남대에서 열린 "생각하는 프로그래밍 대회" 에 출제되었다.

문제 14717번 - https://www.acmicpc.net/problem/14717

섰다는 화투를 이용하여 20장의 카드를 가지고 2명 이상이 경기를 하는 게임이다.

이러한 섰다의 규칙을 단순화한 게임이 바로 '앉았다'이다.

앉았다의 규칙은 1, 2, 3, ... , 9, 10이 쓰인 카드가 각 2장씩 주어지며 총 20장의 카드가 사용되며, 2명이 참가한다.

다음은 앉았다의 경기 방법이다.

1. 두 명의 참가자는 순서대로 20장의 카드 중 무작위로 2장의 카드를 가져온다.
2. 상대방이 이미 가지고 간 카드를 중복해서 가져올 수는 없다. 그리고 자신은 어떤 카드를 가져왔는지 알 수 있지만, 상대방이 어떤 카드를 가져갔는지는 알 수 없다.
3. 서로의 패를 공개한다.
4. 강한 족보의 패를 가진 사람이 이긴다. 만약 두 참가자가 같은 족보의 패를 가졌다면 비긴다.

문제를 요약하자면 다음과 같다.

1. 1 ~ 9 까지 각 2장으로 카드가 구성되어있다. (총 20장)
2. 서로 2장의 카드를 통해 승패가 결정된다.

1 ~ 9 까지의 카드가 각 2장 존재한다는 것을 정확히 인지해야한다.

또한 문제에서 상대방이 먼저 카드를 가지고 갔다는 것을 알 수 있다.

2장을 뽑을 수 있는 경우의 수는 20장 중에 2장을 뽑는 것이 아닌, 18장 중 2장을 뽑는 경우의 수를 구해야한다.

조합 - 순서가 없는 서로 다른 n개에서 r개를 뽑는 경우
18C2 = 153가지

모든 경우의 수를 구했으니, 각 결과에 따른 이길 수 있는 경우의 수를 구해야한다.

예를 들어 1 2 가 주어졌을 경우, 3끗보다 낮은 0, 1, 2끗의 경우의 수를 구하면 된다.

이길 수 있는 상대방의 패는 다음과 같다.

0끗
1 9, 9 1
2 8, 8 2
3 7, 7 3, 3 7, 7 3
4 6, 6 4, 4 6, 6 4

1끗
1 10, 10 1
2 9, 9 2
3 8, 8 3, 3 8, 8 3
4 7, 7 4, 4 7, 7 4
5 6, 6 5, 5 6, 6 5

2끗
2 10, 10 2
3 9, 9 3, 3 9, 9 3
4 8, 8 4, 4 8, 8 4
5 6, 6 5, 5 6, 6 5

경우의 수가 2개 또는 4개인 모습을 볼 수 있다.

그 이유는  각 수는 2장씩 존재하기 때문이다.

예를 들어 상대방이 가진 패가 3, 7 일 경우는 다음과 같다.

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
-------------------------
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
--------------------
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
--------------------
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

상대방의 패에 한개이상 뽑는 카드가 존재한다면, 경우의 수가 2개가 된다.

그렇지 않다면, 4개가 되는 것을 볼 수 있다.

private void solve() {
    DecimalFormat df = new DecimalFormat("0.000");
 
    int a = sc.nextInt();
    int b = sc.nextInt();
    boolean clang = a == b ? true : false;
    int cases = 153; // 18C2
    int cnt = 0;
    int target = (a + b) % 10;
 
    if (clang) {
        cnt = cases - (10 - a);
        System.out.println(df.format(cnt / (cases * 1.0)));
    } else {
        for (int i = 1; i <= 10; i++) {
            for (int j = i + 1; j <= 10; j++) {
                int sum = i + j;
                if (sum % 10 < target) {
                    if (i == a || i == b || j == a || j == b) {
                        cnt += 2;
                    } else {
                        cnt += 4;
                    }
                }
            }
        }
        System.out.println(df.format(cnt / (cases * 1.0)));
    }
 
}