#include #include #include //시발 한개 더 만들어야하나 int n; int w[100]; int v[100]; int max_w; int max_v; int sum_w[100][2]; //0: 해당 물건 선택, 1: 해당 물건 선택안함 int sum_v[100][2]; //0: 해당 물건 선택, 1: 해당 물건 선택안함 int main() { int a = 0, w1, w2, v1, v2; //w1: 0의 무게, w2: 1의 무게, v1: 0의 가치, v2: 1의 가치 scanf("%d %d", &n, &max_w); for(int i = 0; i < n; i++) { scanf("%d %d", &w[i], &v[i]); } for(int i = 0; i < n; i++) { sum_w[a][0] = w[i]; sum_v[a][0] = v[i]; sum_w[a][1] = 0; sum_v[a][1] = 0; //printf("%d %d\n", w[i], v[i]); for(int j = i; j < n; j++) { if(i == j) continue; w1 = sum_w[a][0]; w2 = sum_w[a][1]; v1 = sum_v[a][0]; v2 = sum_v[a][1]; //printf("%d: %d %d %d %d\n", j, w1, v1, w2, v2); //두 경우 모두 max_w보다 작거나 같은 경우 if(w1 + w[j] <= max_w && w2 + w[j] <= max_w) { if(w1 + w[j] == max_w && w2 + w[j] == max_w) { if(v1 > v2) { if(max_v < v1 + v[j]) max_v = v1 + v[j]; } else { if(max_v < v2 + v[j]) max_v = v2 + v[j]; } a++; sum_w[a][0] = sum_w[a-2][1] + w[j]; sum_v[a][0] = sum_v[a-2][1] + v[j]; } else if(w1 + w[j] == max_w && w2 + w[j] != max_w) { if(max_v < v1 + v[j]) { max_v = v1 + v[j]; } a++; sum_w[a][0] = w2 + w[j]; sum_v[a][0] = v2 + v[j]; } else if(w2 + w[j] == max_w && w1 + w[j] != max_w) { if(max_v < v2 + v[j]) { max_v = v2 + v[j]; } a++; sum_w[a][0] = w1 + w[j]; sum_v[a][0] = v1 + v[j]; } else if(v1 > v2) { a++; sum_w[a][0] = w1 + w[j]; sum_v[a][0] = v1 + v[j]; } else if(v1 <= v2) { a++; sum_w[a][0] = w2 + w[j]; sum_v[a][0] = v2 + v[j]; } } //한 쪽만 max_w보다 작거나 같은 경우 else if(w1 + w[j] <= max_w && w2 + w[j] > max_w) { a++; sum_w[a][0] = w1 + w[j]; sum_v[a][0] = v1 + v[j]; } else if(w1 + w[j] > max_w && w2 + w[j] <= max_w) { a++; sum_w[a][0] = w2 + w[j]; sum_v[a][0] = v2 + v[j]; } //둘 다 max_w보다 큰 경우 else if(w1 + w[j] > max_w && w2 + w[j] > max_w){ a++; sum_w[a][0] = sum_w[a-1][0]; sum_v[a][0] = sum_v[a-1][0]; sum_w[a][1] = sum_w[a-1][1]; sum_v[a][1] = sum_v[a-1][1]; continue; } //해당 물건을 선택하지 않았을 경우 if(v1 > v2) { sum_w[a][1] = w1; sum_v[a][1] = v1; } else if(v1 <= v2) { sum_w[a][1] = w2; sum_v[a][1] = v2; } } //printf("%d: %d %d\n", i+1, sum_v[a][0], sum_v[a][1]); if(max_v < sum_v[a][0]) { max_v = sum_v[a][0]; } if(max_v < sum_v[a][1]) { max_v = sum_v[a][1]; } //printf("%d: %d\n", i+1, max_v); a = 0; } printf("%d", max_v); return 0; }

제출 #131750

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: