글 읽기 - 6987 도대체 어디가 문제일까요?? 반례라도 부탁드려요..제발..

angly97 1년 전 0

84퍼에서 틀립니다가 뜨는데 뭐가 문제인지 진자 모르겠요 ㅠㅠㅠㅠㅠ

제발 고수님들 초보 한명 구해주십쇼..

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

def dfs(country, scores):
  # 5번째 나라의 남아있는 승, 무, 패 갯수가 없으면 가능한 경우임
  if country == 5:
    return sum(scores[5]) == 0  
  
  win, draw, lose = scores[country]  # 현재 나라의 남아있는 승, 무, 패 갯수
  country_scores = permutations(list(range(country+1, 6)), 5-country)
  
  copy_scores = [score[:] for score in scores]
  
  for country_score in country_scores:
    is_okay = True
    copy_scores = [score[:] for score in scores]

    # country_score[:win] : 현재 나라가 이긴 나라 번호들
    # country_score[win: win+draw] : 현재 나라와 비긴 나라 번호들
    # country_score[win+draw:] : 현재 나라간 진 나라 번호들
    for i in range(len(country_score)):
      if i < win:
        flag = 2    # i번째 나라는 현재 나라에게 짐
      elif i < win+draw:
        flag = 1    # i번째 나라는 현재 나라에게 비김
      else:
        flag = 0    # i번째 나라는 현재 나라에게 이김

      # 처리할 수 없는 경우, 패스함
      if copy_scores[country_score[i]][flag] == 0:
        is_okay = False
        break
      copy_scores[country_score[i]][flag] -= 1

    if is_okay and dfs(country+1, copy_scores):
      return True
  return False

def sol():
  scores = []
  for _ in range(4):
    info = list(map(int, input().strip().split()))
    scores.append([])
    for i in range(0, 18, 3):
      scores[-1].append(info[i:i+3])
  
  ans = [0, 0, 0, 0]
  for i in range(4):
    if dfs(0, scores[i]):
      ans[i] = 1
    # klj = input()
  return ans
      

if __name__ == '__main__':
  print(*sol())

qwer15417 1년 전 0

저도 초보인데 84퍼에서 막혔다가 해결해서 도움이 될까 싶어 댓글 남깁니다.

님 코드를 제대로 이해하진 못했지만 아마 dfs의 탈출 조건을 정확하게 하셔야할 것 같습니다.

만약 어떤 팀의 승무패의 합이 5가 넘어가는 경우라면 해당 코드는 제대로 동작하지 않을수도 있습니다.

이 경우를 고려해서 다시 한번 짜 보시길 바랍니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

6987 도대체 어디가 문제일까요?? 반례라도 부탁드려요..제발..

angly97 1년 전 0

qwer15417 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말