백준 2407번: 조합

수학 문제 처럼 조합을 푸는 문제다!

실버 3이라서 간단하게 이론을 코드로 그대로 표현했더니 시간 초과가 났다.

 

import sys
from functools import reduce


def fuc(n):
    mylist = [i for i in range(1, n + 1)]
    result = reduce(lambda x, y: x * y, mylist)
    return result


input = sys.stdin.readline

n, m = map(int, input().split())

print(int(fuc(n) / (fuc(m) * fuc(n - m))))

 

 

조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음)

이 공식을 보고 펙토리얼로 재귀함수를 구현하려고 했지만 시간 초과가 났다. 

찾아보니 라이브러리가 있어서 라이브러리를 활용하였다.

import sys
from math import comb

input = sys.stdin.readline
n, m = map(int, input().split())
nlist=[i for i in range(1,n+1)]

print(comb(n,m))

이런식으로 함수를 쓰면 금방 풀어진다.

조합 관련 라이브러리로 math에서 comb를 import해주면 된다!

 

그치만 알고리즘을 잘 활용하려면 라이브러리 말고도 다른 방식으로 시간 초과가 안나는 방법을 배워야된다!