네트워크 유량문제 승부조작에 대해 질문드립니다.

  • wad
    wad

    책의 풀이에서는 선수에서 싱크로 가는 간선의 용량을

    선수가 추가로 가져갈 수 있는 승수로 해놓고,

    canWinWith함수에서 싱크에 도달하는 유량이 남은 경기 수와

    같으면 0번 선수가 totalWins승으로 우승하는 것이 가능하다고

    판단하는데요.

    만약 남은 경기들 중 0번이 플레이 하는 경기가 하나도 없다면,

    0번은 totalWins만큼 이길 수 없음에도 다른 선수들이

    totalWins-1 이하 승수로 분배가 되면 0번이 totalWins만큼

    이기면 된다고 canWinWith함수가 잘못 판단하지 않나요?


    9년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    풀이에 보시면, 0번 선수가 우승하기 위해선 두 개의 조건이 성립해야 한다고 나와 있습니다.

    1. 0번 선수가 남은 경기를 다 이겼을 때 w승 이상 할 수 있다.
    2. 이외의 선수는 전부 w-1승 이하로 리그가 끝나야 한다.

    canWinWith() 함수는 2번 조건만을 확인합니다. 1번 조건은 그 밖에서 확인하셔야 합니다.


    9년 전 link
  • wad
    wad

    아, 감사합니다!


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.