leehanjun   7년 전

알고리즘은 W-1개의 +x와 H-1개의 +y 조합의 개수를 구하려고 했습니다.

예를 들면 W = 3,  H = 4이면 (x, y, y, x, x, y, y) 와 같이 조합의 개수를 구하는 것입니다.

그런데 문제에서, 2 <= W, H <= 100임으로 최악의 시간 복잡도는 200! / (100! * 100!)가 발생하게 됩니다. 

그러면 제한 시간 안에 문제를 풀 수 없는데 어떻게 문제를 풀어야 할까요? 

답변 부탁드립니다.

zasxer   7년 전

(W + H)! / (W! * H!)로 답을 구하면 되겠죠??

바로 구하면 되겠죠!

leehanjun   7년 전

답변 감사합니다.

zasxer   7년 전

넵ㅎ

참고자료는 modular inverse 검색하시면 나와용!

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