[Python] 규영이와 인영이의 카드 게임 ( SWEA D3 6808번 )

규영이와 인영이는 1에서 18까지의 수가 적힌 18장의 카드로 게임을 하고 있다.

한 번의 게임에 둘은 카드를 잘 섞어 9장씩 카드를 나눈다. 그리고 아홉 라운드에 걸쳐 게임을 진행한다.

한 라운드에는 한 장씩 카드를 낸 다음 두 사람이 낸 카드에 적힌 수를 비교해서 점수를 계산한다.

높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수를 얻고,

낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다.

이렇게 아홉 라운드를 끝내고 총점을 따졌을 때, 총점이 더 높은 사람이 이 게임의 승자가 된다.

두 사람의 총점이 같으면 무승부이다.

이번 게임에 규영이가 받은 9장의 카드에 적힌 수가 주어진다.

규영이가 내는 카드의 순서를 고정하면, 인영이가 어떻게 카드를 내는지에 따른 9!가지 순서에 따라

규영이의 승패가 정해질 것이다.

이 때, 규영이가 이기는 경우와 지는 경우가 총 몇 가지 인지 구하는 프로그램을 작성하라.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 아홉 개의 정수가 공백으로 구분되어 주어진다.

각 정수는 1이상 18이하이며, 같은 정수는 없다.

규영이는 정수가 주어지는 순서대로 카드를 낸다고 생각하면 된다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고 한 칸을 띄운 후,

인영이가 카드를 내는 9! 가지의 경우에 대해 규영이가 게임을 이기는 경우의 수와 게임을 지는 경우의 수를

공백 하나로 구분하여 출력한다.

 

---

 

 

Python은 제출 불가인 문제이지만, 공개된 테스트 케이스만이라도 맞춰보자는 생각으로 해결했습니다.

아마 완전탐색으로 인해 시간초과가 발생해서 인 것 같습니다.

실제로 공개 테스트 케이스에 대해 로컬 런타임에서 실행하면 결과 출력에 2~3초의 시간이 소요됩니다.

 

 

모든 경우의 수를 구하라는 부분이 까다롭게 느껴졌으나,

규영이와 인영이의 카드를 각각 나눠서, 순열을 통해 완전탐색을 돌리면 해결될 것이라고 생각했습니다.

 

 

규영이의 카드가 주어지므로, 1부터 18까지의 카드 중 규영이 카드를 제외한 나머지 카드가 인영이의 카드가 됩니다.

이후, 순열을 통해 모든 경우의 수를 비교합니다. 조합이 아닌 이유는 규영이의 카드와 비교를 하게 되며, 단순히 뽑기만 하는 작업이 아니기 때문입니다.

 

 

규영이의 카드와 인영이의 카드를 순서대로 총 9번 비교하고, 이후 주어진 조건에 따라서 승패를 정합니다.

규영이의 카드와 순열 중 현재 인영이의 카드에 대한 결과를 누적합니다.

 

 

 

코드

#swea 6808 규영이와 인영이의 카드 게임
# 중복은 x, 순열 아니면 조합
# 조합은 그저 뽑기만 하므로 [(2, 4, 6, 8, 10, 12, 14, 16, 18)]
# 순열은 순서를 고려
#최대 경우의 수는 9! -> 362880. n^2까지는 통과 -> 이중반복 완전탐색
from itertools import permutations

T = int(input())
for t in range(1,T+1):
    #규영이는 card 순서대로 냄.
    inyoung = [i for i in range(1,19)]
    gyuyoung = list(map(int, input().split()))
    for i in gyuyoung:
        inyoung.remove(i)

    gyu_win =0
    in_win = 0
    for i in list(permutations(inyoung, 9)):
        gg = 0
        yy = 0
        for j in range(9):
            gy = gyuyoung[j]
            iy = i[j]
            if gy > iy: #규영이 카드가 인영이보다 높으면 gg에 합을 저장
                gg += gy + iy
            else: #인영이 카드가 규영이보다 높으면 yy에 합을 저장
                yy += gy + iy
        if gg > yy:
            gyu_win += 1
        else:
            in_win += 1

    print(f"#{t} {gyu_win} {in_win}")