2410번 - 2의 멱수의 합
n의 최대범위인 1,000,000을 넣어봐도 비주얼스튜디오에서는 잘만 돌아가던데,
대체 어디서 런타임 에러가 나는지 모르겠습니다.
참고로 dp[n][m]은 최대가 2^m인 멱수의 합이 n이 되는 경우의 수입니다.
예를 들어 dp[4][2] = 1인데, 이유는 최대가 2^2인 멱수의 합이 4가 되는 경우의 수는 한개이기 때문입니다.
또한 dp[5][1] = 2 인데, 이유는 최대가 2^1인 멱수의 합이 5가 되는 경우는 5 = 2 + 2 + 1, 2+ 1 + 1 + 1 + 1 이기 때문입니다.
저는 dp[i][0] 부터 dp[i][19] 까지를 LINE 13의 for문 마다 계산해주었는데
만약 i > 2^2이면,
dp[ i][2] = dp[i-4][0] + dp[i-4][1] + dp[i-4][2] 로 계산해주었습니다.
이를 for문의 끝인 n까지 계산한다면,
dp[n][0] ~ dp[n][19] 까지 계산되어 있을거고
총 경우의 수의 합은 이를 모두 합친거라고 생각했습니다.
스택 오버플로우네요
dp 배열을 전역으로 놓아보세요.
감사합니다 ㅠㅠ
런타임에러는 배열 잘못 참조에서만 나는줄 알았었는데 아니었군요
댓글을 작성하려면 로그인해야 합니다.
sk7755 6년 전
n의 최대범위인 1,000,000을 넣어봐도 비주얼스튜디오에서는 잘만 돌아가던데,
대체 어디서 런타임 에러가 나는지 모르겠습니다.
참고로 dp[n][m]은 최대가 2^m인 멱수의 합이 n이 되는 경우의 수입니다.
예를 들어 dp[4][2] = 1인데, 이유는 최대가 2^2인 멱수의 합이 4가 되는 경우의 수는 한개이기 때문입니다.
또한 dp[5][1] = 2 인데, 이유는 최대가 2^1인 멱수의 합이 5가 되는 경우는 5 = 2 + 2 + 1, 2+ 1 + 1 + 1 + 1 이기 때문입니다.
저는 dp[i][0] 부터 dp[i][19] 까지를 LINE 13의 for문 마다 계산해주었는데
만약 i > 2^2이면,
dp[ i][2] = dp[i-4][0] + dp[i-4][1] + dp[i-4][2] 로 계산해주었습니다.
이를 for문의 끝인 n까지 계산한다면,
dp[n][0] ~ dp[n][19] 까지 계산되어 있을거고
총 경우의 수의 합은 이를 모두 합친거라고 생각했습니다.