404_forbidden   5년 전

b개의 바구니에 n개의 숫자가 있을 때 이를 차례대로 연결하여 조합할 수 있는 경우의 수를 구합니다.

단, 조합한 수의 결과를 x로 나눈 나머지가 k인 경우의 수만 출력하도록 하고

경우의 수를 10^9 +7 로 나눈 나머지를 결과값으로 출력합니다.

--

문제에서 2<=x <=101 이고

x로 나눈 나머지가 k인 경우를 구하기 때문에

0~ 100 범위의 값에서 

i-1번째 바구니까지 블록을 뽑아 만든 수를 x로 나눈 나머지가 h 일 때 => 경우의 수를 old[h]에 기록하고

이를 이용하여

i번째 바구니에서 뽑은 블록 j를 연결하여 만든 값 (h*10+ arr[j])%x 번째 cur 배열에 이 경우의 수를 더합니다. 

이 때 10^9+7 로 나눈 나머지를 기록해야합니다.

한 바구니의 사이클이 돌 때마다 old-cur 포인터를 바꾸고 cur 배열을 0으로 초기화합니다 (i+1번째 바구니를 구하기 위함)

b번째까지 사이클을 돌고 old[k]에 접근하면 원하는 값을 얻을 수 있을거라고 생각했는데

런타임 에러가 나버리네요

도움을 부탁드립니다.

luniro   5년 전

삼중 for문에서 10^9 * 50000 * x면 너무 오래걸리지 않나요?

404_forbidden   5년 전

네 맞습니다 혼자 삽질하고 실패해서 읽기만하고 답글을 못달았었네요 죄송합니다.

모든 주머니에 같은 블록셋이 있어서 제곱단위로 블럭의 경우의수를 구해서  ( 1주머니 x 1주머니 , 2주머니 x 2주머니, 4주머니 x 4주머니.. )

연산을 단축시켜서 해결해보려고합니다.

런타임 에러는 메모리 문제였던 것 같습니다.

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