6987 월드컵

💡문제 분석 요약

• 월드컵 조의 경기 결과를 보고, 해당 결과가 나올 수 있는 결과인지 아닌지 판단한다.
• 경기 결과는 4개 조에 대해서 주어진다.
• 한 조에 6팀이 속한다.

💡알고리즘 설계

• 백트래킹으로 모든 경우의 수를 다 구할까 생각했었다.
• 이는 3^15 경우의 수인데 이론상 가능하다고 생각했다.

💡코드

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

answer = []

# 가능한 모든 게임 조합 - 총 15개 게임 (0,1), (0,2), ... , (4,5)
game = list(combinations(range(6), 2))


def backTracking(round):
    global ans
    if round == 15: # 모든 게임을 다 처리한 경우
        ans = 1
        # 각 국가의 승/무/패 결과가 모두 소진된 경우만 유효함
        for sub in result:
            if sub.count(0) != 3:  # 승, 무, 패가 모두 0이어야 함
                ans = 0
                break
        return

    # 현재 게임에서의 두 팀
    t1, t2 = game[round]

    # 가능한 경기 결과 (승/패, 무/무, 패/승)
    for x, y in ((0, 2), (1, 1), (2, 0)):
        # t1이 x 결과를, t2가 y 결과를 가질 수 있는지 확인
        if result[t1][x] > 0 and result[t2][y] > 0:
            # 경기 결과 반영
            result[t1][x] -= 1
            result[t2][y] -= 1

            # 다음 게임으로 넘어감
            backTracking(round + 1)

            # 백트래킹: 원래 상태로 되돌림
            result[t1][x] += 1
            result[t2][y] += 1

# 4번의 결과에 대해 처리
for _ in range(4):
    data = list(map(int, input().split()))
    result = [data[i:i + 3] for i in range(0, 18, 3)]
    ans = 0
    backTracking(0)
    answer.append(ans)

print(*answer)

💡시간복잡도

• 모든 경기를 다 탐색해야하므로 O(3^15)

💡 틀린 이유

• 문제가 너무 어려웠다... 그리고 3^15이나 걸린다고 생각해서 다른 풀이를 생각하는 것도 오래걸렸다.

💡 틀린 부분 수정 or 다른 풀이

• 풀이 방식, 코드가 좀 다른 풀이는 있었지만 대부분 같은 맥락의 풀이였다.

💡 느낀점 or 기억할정보

• 시간복잡도를 먼저 계산해보는 게 왜 중요한지 깨닫게 되었다. 계산해보고 안되겠다 싶으면 바로 다른 풀이로 떠나야한다. 매우 중요 !!