1226번: 국회

https://www.acmicpc.net/problem/1226

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_S = 100000;
int n, ck[MAX_S + 1], from[MAX_S + 1], p[MAX_S + 1], sum;
struct st {
    int w, idx;
    bool operator<(st i) const {
        return w > i.w;
    }
}s[300];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &s[i].w);
        s[i].idx = i + 1;
        sum += s[i].w;
    }
    sort(s, s + n);
    ck[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = MAX_S; j >= s[i].w; j--) {
            if (j - s[i].w <= sum / 2 && ck[j - s[i].w] && !ck[j]) {
                ck[j] = 1;
                from[j] = j - s[i].w;
                p[j] = s[i].idx;
            }
        }
    }
    for (int i = MAX_S; i >= 0; i--) {
        if (ck[i]) {
            int cnt = 0;
            for (int j = i; j != 0; j = from[j]) cnt++;
            printf("%d\n", cnt);
            for (int j = i; j != 0; j = from[j])
                printf("%d ", p[j]);
            break;
        }
    }
    return 0;
}