테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 특별상 눈치게임 ======

===== 풀이 =====
  * 팀의 수를 n, 정수의 범위를 m이라고 하자.
  * n과 m이 작아서 [[https://github.com/ssu-sccc/2025scon/blob/main/editorial-slide.pdf|에디토리얼]]의 풀이처럼 O(n + m^4)의 브루트포스로도 풀린다
  * 좀더 효율적으로 풀려면, 특별상에 해당되는 점수를 X로 만드는 정수 조합의 개수를 각각 세어주는 방식으로 접근하자
  * 내가 X점으로 특별상을 받기 위해서 반드시 선택해야 하는 수는
    * X => 당연하다
    * X보다 큰 수중에서 1명만 선택한 수 => 내가 그 수를 안고르면 그 수가 특별상이 되므로..
  * 그리고 선택하면 안되는 수는
    * X보다 큰 수중에서 아무도 선택하지 않은 수 => 그 수를 고르면 X가 아닌 그 수가 특별상이 된다.
  * 그러면 X점으로 특별상을 받을수 있는 조합의 개수는 comb(100 - {선택하면 안되는 수의 개수} - {반드시 선택해야 하는 수의 개수}, 3 - {반드시 선택해야 하는 수의 개수}) 이다
  * 따라서 먼저 각 수에 대해서 선택팀의 수를 구해놓은 다음에, X를 100부터 1까지 줄여가면서, 무조건 골라야 하는 수의 개수와 고르면 안되는 수의 개수를 관리하며 위의 식을 계산하면 된다. 각 X에 대한 값을 O(1)에 구할 수 있으므로 (comb(n,k)은 k가 2이하이므로 O(1)에 계산가능) 총 시간복잡도는 O(n+m)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 33911. 특별상 눈치게임".

- Problem link: https://www.acmicpc.net/problem/33911
- Solution link: http://www.teferi.net/ps/problems/boj/33911

Tags: [ad hoc]
"""

import math


def main():
    N = int(input())
    counter = [0] * 101
    for _ in range(N):
        A, B, C = [int(x) for x in input().split()]
        counter[A] += 1
        counter[B] += 1
        counter[C] += 1

    answer = 0
    cannot_select_count = must_select_count = 0
    for i in range(100, 0, -1):
        if counter[i] == 0:            
            answer += math.comb(
                99 - cannot_select_count - must_select_count,
                2 - must_select_count,
            )
            cannot_select_count += 1
        elif counter[i] == 1:
            must_select_count += 1
            if must_select_count >= 3:
                break

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_3}}