"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); 이 안 걸려드네요. 데이터가 약합니다.

그런것 같네요