emptyshow   1년 전

N*M 배열에서 1,1 에서 N,M 까지 가는 모든 경로의 수를 계산하는데

dp[i][j] = dp[i-1][j] + dp[i][j-1] 이점화식을 사용해서 N, M 이 적은수는 배열로 풀면 될것같은데..
1 1 1 1
1 2 3 4
1 3 6 10
1 4 10 20

문제는 N M 이 커질때 또 다른방법이 있는지 궁금합니다. N, M 이 각각 100,000 이 넘어가면 굉장히 오랜시간이 걸렸습니다.
배열을 구성하는데에도 큰메모리가 필요한데,,

이렇게 큰수를 구할땐 저점화식을 사용한 DP 말고, 다른 방법이 있을까요??

yukariko   1년 전

dp를 계산하는 순서를 잘 고려해본다면

가로 두줄만을 가지고 답을 찾을 수 있습니다.

그리고 N, M이 모두 100,000 이라면 애초에 입력조차 받아올 수 없을것으로 보이네요.

emptyshow   1년 전

고민해보겠습니다!!

shjgkwo   1년 전

음.. 제가 이해한게 맞다면 DP로 풀지 않아도, 중복조합을 사용해서 풀면 될것 같습니다.

왼쪽이 L 아래가 D 라고 두었을때 N*M이 5*4 라면 LLDDLDDLL 이런식으로 배치하는 방법의 개수를 구하는 문제로 바꿀 수 있습니다.

중복조합 식으로 풀면 (N+M)!/N!M! 이 되겠네요. N, M이 10만이면.. 모듈러 연산이 필요하지 않을까요..?

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