콤비네이션 이거 정말 골치아프네여

[whatugo..(sibal214)]

N, M 의 입력이 최대 10만인데

테스트 케이스 도는 와중에 타임아웃뜨네여...

ㅠㅠ

[심심(163.239)]

나도 여기서 막힘 조합계산 빨리하는법 앎?

[whatugonnado(sibal214)]

알면 시간초과 안났겠져? 나름 빠르게 짠거 같은데 1.00027 초 타임아웃 이렇게 팝업 뜨던데

[심심(163.239)]

ㅋㅋ 나랑 똑같네 난 f(n, k) = f(n, k-1)*(n-k+1)/k 로 계산했는데 혹시 더 빠른 방법 있오?

[?(218.50)]

피자 얘기 아니었냐

[whatugonnado(sibal214)]

위에처럼 재귀로 짜버리면 너무 오래걸려염!

[이거(175.192)]

시간복잡도 N*logMOD로 됨.

[이거(175.192)]

그리고 N,M 10만이 아니라 100만

[whatugonnado(sibal214)]

난 아예 테스트케이스 값 받기 전에 팩토리얼 202만개짜리 배열 만들어서 넣고 그거 써먹는 방법으로 했어염!

[이거(175.192)]

202만? 200만2 아님? 암튼 님 말대로 미리계산하는건 필수.. 콤비네이션 계산은 어떤식으로 돌아가는지 궁금하다

[심심(210.178)]

나도 메모이제이션해보려고 2차원배열 짜서 했는데 N, M이 십만이잖아? 컴파일하면 너무 메모리가 크다고나와서 방법을 바꾼거거든. 너는 일차원배열 200만개 만들어서 기록한거임?

[whatugonnado(sibal214)]

팩토리얼한 값만 MOD연산해서 집어넣고했는데 이때 문제가 좀 있는데 그건 댓글로 말고 다음 글로 이어서 써볼게염

[심심(163.239)]

오오 기대하겠음