chatterboy   2년 전

C[m,c] = C[m,c-1] + C[m-D(c),c] 를 구현했는데..

메모리 제한이 4MB이더군요. 어떻게 해야하나요..

알려주신다면 감사하겠습니다 ㅜㅜ

dcrgkev   2년 전

DP문제인것같은데 그러면 슬라이딩 윈도를 쓰시면 될것같네요

august14   2년 전

슬라이딩 윈도우가 아니고 점화식에서 c-2이하는 더 이상 안보니까 1차원 배열 두개만으로 할수있는겁니다.

baekjoon   2년 전

덧 붙이자면 점화식 순서를 바꿔서

C[c,m] = C[c-1,m] + C[c,m-D(c)] 로 바꾸면

c를 채울때는 c-1만 참조한다는 사실을 알 수 있습니다.

따라서, C[c][] = A, C[c-1] = B 로 나타내면 점화식을 A[m] = B[m] + A[m-D(c)] 로 바꿀 수 있습니다.

그럼 이제 A와 B배열만 가지고 문제를 풀 수 있게 됩니다. A 배열을 모두 채운 다음에는 내용을 모두 B에 복사하는 형식으로요.

아니면, C[2][m] 크기의 배열을 잡고 문제를 풀 수도 있습니다. 이런 경우에는

C[c%2,m] = C[(c-1)%2,m] + C[c%2, m-D(c)] 로 풀면 1차원 배열 두 개로 풀 수 있습니다. 

(c-1)%2는 음수가 나올 수 있기 때문에 (c+1)%2로 써도 됩니다. 

chatterboy   2년 전

답변 주신 분들 모두 감사합니다:)

zagame   6달 전

C[c,m] = C[c-1,m] + C[c,m-D(c)]

이 점화식에서 D(c)가 의미하는게 뭔지 여쭤봐도 될까요 ㅠㅠ

chatterboy   6달 전

zagame

c번째 동전의 금액입니다~

zagame   6달 전

저건 의미상 저런 점화식이 나온 거지요..?

실제로 c번째 동전 금액을 1번, 2번.... k번 쓸 수 있을 때 까지 

for문 돌려야 되는 거 아닌가요?

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