2293번 - 동전 1
메모리 보니깐 우선 탑다운 방식으로 푸는 것을 저격한 것 같은데 거기까지는 이해할 수 있습니다.
근데 바텀업으로 풀어도 메모리 초과가 나네요 1년전 같은 코드로 제출한 기록은 맞았습니다 떴습니다.
1년사이에 기본 메모리가 증가한 건지는 모르겠지만 너무 빡빡한 메모리 제한 인 것 같아요.
8MB로 수정 제안드립니다.
"vector > dp(n, vector(k+1, 0))"이 들어있는 코드가 메모리를 3KB밖에 안 쓴다는 게 오히려 신기하네요. 단순히 바텀업만 써야 되는 게 아니라 O(K)의 메모리만으로 풀어야 합니다.
위 댓글에 오타: 3KB -> 3MB
1년 전에 맞으신 코드를 그대로 제출해 봤는데 2172KB로 잘 돌아갑니다.
vector<vector<int>(n, vector(k+1, 0))가 어마어마하게 효율적이라고 밖에는 설명이 안되는건가요? 신기하네
vector<vector<int>(n, vector(k+1, 0)) 는 O(nk)의 메모리이고, 이 문제의 의도는 1차원의 k짜리 배열만 사용해서 푸는 것입니다.
http://boj.kr/2bf9b84fe8354c21...
이 코드를 보면 O(NK)로 풀었는데 맞았습니다. 나옵니다.
벡터 내부에서 먼가 엄청난 일이 일어나는 것 같네요...
n과 k+1 말고 100과 10000으로 벡터를 잡았더니 메모리 초과가 뜨는 거로 보아 데이터가 약한 것 같습니다.
if (n * k > 500000) while (1); 이 안 걸려드네요. 데이터가 약합니다.
그런것 같네요
댓글을 작성하려면 로그인해야 합니다.
upple1 5년 전
메모리 보니깐 우선 탑다운 방식으로 푸는 것을 저격한 것 같은데 거기까지는 이해할 수 있습니다.
근데 바텀업으로 풀어도 메모리 초과가 나네요 1년전 같은 코드로 제출한 기록은 맞았습니다 떴습니다.
1년사이에 기본 메모리가 증가한 건지는 모르겠지만 너무 빡빡한 메모리 제한 인 것 같아요.
8MB로 수정 제안드립니다.