[Greedy] 저울

출처 : http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=2499

 2011.KOI.전국.초등부

#include 
#define DEBUG 1
#define MAX_WEIGHTS 1000

void SetInputFromFile(const char* fileName, int *num_weights, int *weights);
void PrintAnswerToFile(const char* fileName, int min_umw /*minimum unmeasurable weight*/);
int GetMinUnmeasurableWeight(const int num_weights, int *weights);
void SortWeight(int num_weights, int* weights);

int main() {

    int num_weights;
    int weights[MAX_WEIGHTS];

    SetInputFromFile("input.txt", &num_weights, weights);
    PrintAnswerToFile("output.txt", GetMinUnmeasurableWeight(num_weights, weights));

    return 0;
}

void SetInputFromFile(const char* fileName, int *num_weights, int *weights) {
    int i;
    FILE *input = fopen(fileName, "r");
    if (input == NULL) {
        fprintf(stderr, "Can NOT open file: \n", fileName);
        goto bail;
    }

    //TODO:
    fscanf(input, "%d", num_weights);
    for (i = 0; i < *num_weights; i++) {
        fscanf(input, "%d", &(weights[i]));
    }
  
    fclose(input);
    return;
bail:
    if (input != NULL) fclose(input);
}

void PrintAnswerToFile(const char* fileName, int min_umw /*minimum unmeasurable weight*/) {
    FILE *output = fopen(fileName, "w");
    if (output == NULL) {
        fprintf(stderr, "Can NOT open file: \n", fileName);
        goto bail;
    }

    fprintf(output, "%d\n", min_umw);
    fclose(output);
    return;
bail:
    if (output != NULL) fclose(output);
}

int GetMinUnmeasurableWeight(const int num_weights, int *weights) {
    int pmr; // possible_measurement_range
    int nw;  // new_weight
    int i;

    SortWeight(num_weights, weights);

    pmr = 0;
    for (i = 0; i < num_weights; i++) {
        nw = weights[i];
        if (nw - 1 > pmr) {
            return pmr + 1;
        }
        pmr += nw;
    }
    return pmr + 1;
}

void SortWeight(int num_weights, int* weights) {
    int i, j, temp;

    for (i = 0; i < num_weights; i++) {
        for (j = i + 1; j < num_weights; j++) {
            if (weights[i] > weights[j]) {
                temp = weights[i];
                weights[i] = weights[j];
                weights[j] =  temp;
            }
        }
    }
}