sgc109   1년 전

동전의 단위를 입력받아 내림차순 정렬을 하고 큰 단위의 동전부터 최대 사용가능 개수부터 0개까지 하나씩줄여가며 그 아래 단위에도 재귀적으로 조합하여 가장 마지막 단위까지 도달했을때 합이 만들고자하는 금액 k 와 같다면 세는 식으로 해서 계산하게했고

D(i,j) = 현재까지 i원을 만들었고 개수를 정해야하는 단위가 coin[j] 일때 최종금액 k를 만드는것이 가능한 경우의 수


로 하여 계산을 하고자했는데 메모리제한이 4MB 인데 unsigned int dp[10000][100] 만 해도 4MB 가 되어 메모리 초과가 뜹니다.. 어떻게 개선하면 좋을까요?


@hongjun7

nosqeil24   1년 전

dp[k][i] 를 채우기 위해서는 dp[k'][i-1] (0<=k'<=k)의 값이 필요합니다.

즉, dp[k][i] 를 채우기 위해서 dp[k'][0~i-2] 에 있는 값은 필요가 없다는 사실을 이용하여

다이나믹 배열을 모듈라 연산을 통해 dp[10001][2] 로 줄일 수 있습니다.

dp[i][k] = sum(dp[i-1][k') <=> dp[i%2][k] = sum(dp[(i-1)%2][k'] (모듈라 연산 이용)

슬라이딩 윈도우 기법으로 검색해보세요

nosqeil24   1년 전

제 소스입니다. 혹시 이해가 안되신다면 참고해보세요!

indioindio   1년 전

5, 3, 1원이 있는데 10원짜리를 만들고자 한다면

10원을 만드는 경우의 수는 5원을 만드는 경우의 수 + 7원을 만드는 경우의 수 + 9원을 만드는 경우의 수라는 걸 생각해보시면 도움이 될 것 같네요

sgc109   1년 전

indioindio

5, 3, 1 원으로

10원을 만드는 경우의 수 = 7

9원을 만드는 경우의 수 = 6

7원을 만드는 경우의 수 = 4

5원을 만드는 경우의 수 = 3


7 = 6 + 4 + 3 ???


음 뭔가 잘못된것같네요

sgc109   1년 전

nosqeil24


아 전에 본능적으로 모듈라연산으로 메모리 초과를 해결한적이 있었어서 이걸 쓸려고했었는데

이 문제와 같은 경우에는 dp 의 모든 원소가 계속 사용된다고 생각해서 사용하지못했는데


'dp[k][i] 를 채우기 위해서는 dp[k'][i-1] (0<=k'<=k)의 값이 필요합니다.' 이 부분이 이해가 갈듯말듯합니다..


저와 D(i,j) 를 다르게 잡으셔서 헷갈리는것 같기도하고.. 저는 dp 에서 열의 인덱스가 작을 수록 더 크거든요.. 아니면 그냥 제가 이해를 잘못하는건가요 ㅠㅠ 으 머리속이 꼬인기분이에요


indioindio   1년 전

아아 제가 다른 문제랑 헷갈려서 표현을 이상하게 했네요 ㅋㅋ

각 동전 n원에 대해서, k원을 만드는 법은

k - n의 경우의 수와 같은 거였네요(이 표현도 쓰고보니 조금 이상한거같지만)

1 3 5로 10원을 만든다면

1원으로는 1 ~ 10까지 올라가면서 한 가지 경우로 만들수 있고(0원을 내는 경우의 수가 1이라면요)

3원으로 3원을 만든다면, 3원을 1동전을 이용한 한 가지 방법으로 이미 만들수 있으므로 2… 이렇게 하시면 될 듯 합니다

현재까지 등장한 동전으로 만들 수 있는 금액의 경우의 수를 가지고 있으므로 1차원 배열로 할 수 있을 것 같네요

appa   1년 전

1차원으로 정의하여 누적하며 계산할 수 있습니다.

sgc109   1년 전

@hongjun7


아... 이런방법이...

감사합니다!

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