Counting Quartets

https://rosalind.info/problems/cntq/

ROSALIND | Counting Quartets

 

 이 문제는 unrooted binary tree에 있는 leaf의 개수와 newick 형식으로 나타내진 tree가 주어지고 이 중 만들어질 수 있는 quartet의 개수를 구하는 문제이다.

 이 문제는 언뜻 보면 split들을 구하고 이 split들을 기준으로 2개씩 골라서 quartet을 만드는 문제처럼 보인다. 하지만 곰곰히 생각해본다면 unrooted binary tree는 가장 작은 taxa가 leaf가 2개이므로 아무렇게나 4개를 골랐을 때 그 중 3개 이상이 하나의 taxa에 있을 수 밖에 없는 상황이 없다. 이 뜻은 이 문제는 그냥 단순히 조합의 개수를 출력하는 문제가 된다.

from math import comb


def main():
    n = int(input())
    print(comb(n, 4) % 1000000)

main()