Coin Change와 관련된 문제가 안 풀려 질문 올립니다.

Question

안녕하십니까, 백준에서 문제를 풀던 중 틀린 이유를 찾지 못하여 질문 올립니다. 주어진 문제는 백준 25958번의 '예쁜수' 문제입니다.이때 '예쁜수'란 주어진 숫자의 각 자릿수의 합이 원래 숫자의 약수인 숫자를 말하며, 문제는 주어진 숫자 M을 예쁜수의 합으로만 나타내는 경우의 수를 구하고, 이를 소수 K로 나누어 출력하라고 합니다.위 정의에서 '합을 만드는 경우의 수'라는 원리에 따라 Dynamic Programming의 Coin Change와 관련된 문제임을 알고, M이하의 예쁜수는 모두 Coin으로 지정하고, 답을 M을 만드는 Coin의 경우의 수로 생각해서 문제를 풀었습니다. 하지만 문제의 주어진 예제는 모두 맞았지만 계속 답은 틀렸다고 나와, 문제 풀이 이외에 배열 범위, 함수 범위 등에서 오류를 찾으려 했으나, 제 눈에는 틀린 점을 찾지 못하여 이렇게 질문 올립니다.언어는 C++17을 사용하였습니다.#include using namespace std; #define ull unsigned long long // 주어진 수가 예쁜수인지 판단하는 함수 bool isPretty (int n) { int sum = 0, n2 = n; while (n != 0) { sum += n % 10; n /= 10; } if (n2 % sum == 0) { return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int m, k; cin >> m >> k; // m 이하의 자연수들 중 예쁜수이면 coins 배열에 더하기 vector coins; for (int i = 1; i <= m; ++i) { if (isPretty(i)) { coins.push_back(i); } } // 예쁜수의 합이 m이 되는 경우의 수 구하기 vector ways (m + 1, 0); ways[0] = 1; for (int coin : coins) { for (int j = 0; j < m + 1; ++j) { if (coin <= j) { ways[j] += ways[j - coin]; } } } // 주어진 경우의 수를 k로 나누어 출력하기 cout << ways.back() % k; return 0; }C++ 공부를 시작한지 얼마 되지 않아서, 고수분들께 이렇게 질문드립니다.

엡실론 · Answer

ways[j] += ways[j-coin] 에서 오버플로우가 나는게 아닐까요? 더하고 k로 나눠 저장하세요.

Coin Change와 관련된 문제가 안 풀려 질문 올립니다.

1개의 답변

Q&A 목록