[BOJ] 월드컵 (no.6987)

문제

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

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

입력

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

출력

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

🤔 생각

• 접근을 잘하면 쉬운 문젠데, 아이디어를 생각해내기가 어려웠던 문제다. 사실 풀고 난 지금도 이게 왜 실버 티어인지 모르겠다...

• 일단 6팀 간 매치는 미리 조합으로 구해두고,

• 백트래킹으로 승/무/패를 1씩 빼가면서 전체 합계가 0이 되는게 가능한지 구하면 된다.

📌 내 풀이

from itertools import combinations
import sys
input = sys.stdin.readline

def solve(round):
    global ans
    if round == 15:
        ans = 1
        for sub in res:
            if sub.count(0) != 3:
                ans = 0
                break
        return
        
    t1,t2 = game[round]
    for x,y in ((0,2), (1,1), (2,0)):
        if res[t1][x] > 0  and res[t2][y] > 0:
            res[t1][x]-=1; res[t2][y]-=1
            solve(round+1)
            res[t1][x]+=1; res[t2][y]+=1


answer = []
game = list(combinations(range(6),2))
for tc in range(4):
    tmp = list(map(int, input().split()))
    res = [tmp[i:i+3] for i in range(0,16,3)]
    ans = 0
    solve(0)
    answer.append(ans)

print(*answer)

✔ 회고

• 인덱싱 한번 삐끗해서 그거 찾느라고 애 좀 먹었다..
• 이런 아이디어도 백트래킹으로 해결할 수 있구나 싶은 문제였다!