PACKING 문제 질문있습니다..! takun612 아래는 오답처리 된 코드인데요, MAXN을 101로 바꾸니 정답처리가 되네요.. N의 범위가 (1≤N≤100) 입니다. 그런데 저는 0~99까지로 100개의 단어를 표현하려고 생각하고 코드를 짰는데, 왜 101로 해야 되는지 잘 모르겠습니다.. 왤까요? 입력으로 N에 100이 들어와도 MAXN이 100이어도 충분하지 않나요? ㅠㅠ #include<iostream> #include<string> #include<algorithm> #include<vector> #define MAXN 100 using namespace std; int C; int N, W; string name[MAXN]; int cap[MAXN]; int need[MAXN]; int memo[MAXN][1001]; vector<string> list; int setmemo(int id, int weight){ int& ret = memo[id][weight]; if (ret != -1) return ret; //기저사례: id가 끝까지 도달 if (id == N) return 0; ret = max(ret, setmemo(id + 1, weight)); if (weight >= cap[id]) ret = max(ret, setmemo(id + 1, weight - cap[id]) + need[id]); return ret; } void reconstruct(int id, int weight){ if (id == N) return; //리스트에 없음 if (setmemo(id, weight) == setmemo(id + 1, weight)) { reconstruct(id + 1, weight); } //리스트에 있음 else { list.push_back(name[id]); reconstruct(id + 1, weight - cap[id]); } } void solve() { //1. 리스트 생성 reconstruct(0, W); //2. 리스트 출력 cout << setmemo(0, W) << " " << list.size() << endl; if (list.size() == 0) return; for (int i = 0; i < list.size() - 1; i++) { cout << list[i] << endl; } cout << *list.rbegin(); } int main() { cin >> C; while (C--) { //메모 초기화 for (int i = 0; i < MAXN; i++) { for (int j = 0; j < 1001; j++) { memo[i][j] = -1; } } list.clear(); cin >> N >> W; for (int i = 0; i < N; i++) { cin >> name[i] >> cap[i] >> need[i]; } solve(); if (C != 0) cout << endl; } return 0; } 8년 전
2개의 댓글이 있습니다. JongMan int& ret = memo[id][weight]; if (ret != -1) return ret; //기저사례: id가 끝까지 도달 if (id == N) return 0; 이 부분의 순서에 주의해서, 범위를 벗어난 접근을 하고 있지 않은지 확인해 보세요. 8년 전 link takun612 아..! 감사합니다~! 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
takun612
아래는 오답처리 된 코드인데요, MAXN을 101로 바꾸니 정답처리가 되네요..
N의 범위가 (1≤N≤100) 입니다. 그런데 저는 0~99까지로 100개의 단어를 표현하려고 생각하고 코드를 짰는데, 왜 101로 해야 되는지 잘 모르겠습니다.. 왤까요? 입력으로 N에 100이 들어와도 MAXN이 100이어도 충분하지 않나요? ㅠㅠ
8년 전