5569번 - 출근 경로
알고리즘은 W-1개의 +x와 H-1개의 +y 조합의 개수를 구하려고 했습니다.
예를 들면 W = 3, H = 4이면 (x, y, y, x, x, y, y) 와 같이 조합의 개수를 구하는 것입니다.
그런데 문제에서, 2 <= W, H <= 100임으로 최악의 시간 복잡도는 200! / (100! * 100!)가 발생하게 됩니다.
그러면 제한 시간 안에 문제를 풀 수 없는데 어떻게 문제를 풀어야 할까요?
답변 부탁드립니다.
(W + H)! / (W! * H!)로 답을 구하면 되겠죠??
바로 구하면 되겠죠!
답변 감사합니다.
넵ㅎ
참고자료는 modular inverse 검색하시면 나와용!
댓글을 작성하려면 로그인해야 합니다.
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!)가 발생하게 됩니다.
그러면 제한 시간 안에 문제를 풀 수 없는데 어떻게 문제를 풀어야 할까요?
답변 부탁드립니다.