[문제해결기법] 게으른 거미 (fail)

//140918 Corder by YoWu. (uyu423@gmail.com)
//This C source code has been tested by Visual Studio 2013 in D409

#include "stdio.h"
#include "stdlib.h"
#include "time.h"

#define MAX_LEN 1000000
#define TRUE 1
#define FALSE 0

typedef struct muk2 {
    unsigned int size;    // 1 <= size <= 10,000
    unsigned int point;  // 0 <= point <= 1,000,000
    unsigned int st;
    unsigned int ed;
    int bool;
}spider;

void setFood(FILE *fo, FILE *fw, unsigned int total, unsigned int dist, spider *food,
    unsigned int *dist_st, unsigned int *dist_ed) {

    unsigned int i;
    for (i = 0; i < total; i++) {
        fscanf_s(fo, "%d", &food[i].size);
        fscanf_s(fo, "%d", &food[i].point);
        if (food[i].point > *dist_ed)
            *dist_ed = food[i].point;
        if (food[i].point < *dist_st)
            *dist_st = food[i].point;
        food[i].ed = food[i].point + dist;
        if ((int)food[i].point - (int)dist > 0)
            food[i].st = food[i].point - dist;
        else
            food[i].st = 0;
    }
}

int checkFood(unsigned int num, spider *food, unsigned int total) {
    unsigned int i;
    int isTRUE = 0;

    for (i = 0; i < total; i++) {
        if (num >= food[i].st && num <= food[i].ed) {
            food[i].bool = TRUE;
            isTRUE = 1;
        }
        else
            food[i].bool = FALSE;
    }

    return isTRUE;
}

unsigned int sumFood(unsigned int dist, unsigned int total, spider *food) {
    
    unsigned int i;
    unsigned int sum = 0;
    
    for (i = 0; i < total; i++) {
        if (!food[i].bool)  continue;
        sum += food[i].size;
    }

    return sum;
}

unsigned int moveSpider(unsigned int dist, unsigned int dist_st, unsigned int dist_ed, spider *food, unsigned int total) {
    unsigned int i;
    int run;

    unsigned int max = 0;
    unsigned int tmp;

    for (i = dist_st; i <= dist_ed; i++) {
        run = checkFood(i, food, total);
        if (run == FALSE)   continue;
        tmp = sumFood(dist, total, food);
        if (max < tmp)  max = tmp;
    }

    return max;
}

void printFood(unsigned int total, spider *food, unsigned int dist_st, unsigned int dist_ed) {

    unsigned i;
    for (i = 0; i< total; i++) {
        printf("Food[%d] point : %d ", i, food[i].point);
        printf("Food[%d] size : %d ", i, food[i].size);
        printf("Food[%d] st_point : %d ", i, food[i].st);
        printf("Food[%d] ed_point : %d ", i, food[i].ed);
        printf("Food[%d] bool : %d ", i, food[i].bool);
    }
    printf("first Food Point : %d ", dist_st);
    printf("last Food Point : %d ", dist_ed);
}

int main(void) {

    clock_t time_st = clock(), time_ed;

    FILE *fo;
    FILE *fw;

    fopen_s(&fo, "input.txt", "r");
    fopen_s(&fw, "output.txt", "w");

    unsigned int total;  // 1 <= total food number <= 100,000
    unsigned int dist;    // 1 <= spider's distance <= 2,000,000
    unsigned int dist_st = MAX_LEN;
    unsigned int dist_ed = 0;
    unsigned int result;
    spider *food;

    fscanf_s(fo, "%d", &total);
    fscanf_s(fo, "%d", &dist);

    food = (spider *)calloc(total, sizeof(spider));

    setFood(fo, fw, total, dist, food, &dist_st, &dist_ed);
    result = moveSpider(dist, dist_st, dist_ed, food, total);
    fprintf(fw, "%d", result);
    time_ed = clock();
//  printFood(total, food, dist_st, dist_ed); //debug check function
//  printf("Process Time : %f ", ((double)(time_ed - time_st)) / CLOCKS_PER_SEC);
}

처음 main() 에서 파일 입출력과 변수에 대한 설정을 한 뒤 총 먹이 수와 거미의 이동 범위를 입력받는다. 

다음으로 setFood 함수를 호출해 spider 구조체 Food 변수에 먹이에 대한 정보를 저장한다. 

그리고 최종 출력 데이터를 반환 값으로 가지는 moveSpider 함수를 호출하는데, 

여기서x 좌표의 값을 하나 씩 이동하며 거미가 해당 위치에서 총 이동할 수 있는 거리에 위치한 먹이들의 bool 값을 1로 변경한 뒤, 

전체 Food에 1이 하나라도 있을 경우 sumFood 함수를 호출해 해당 위치를 포함하는 모든 먹이의 총 합계를 구한다. 

그리고 나서 기존의 max값과 비교해 새로운 값이 더 클 경우 값을 교체하고 마지막에 output.txt 에 출력한다.

---

결과론 적으로 망한 알고리즘이다. 테스트 케이스가 적을 때는 잘 작동하지만 케이스가 많아질수록 n타임에 비례해 시간이 더 걸리는 전형적인 비효율적 알고리즘이다. 

생각을 많이 안한 탓일까. 코딩 후에 생각해보니 테스트 케이스가 커질 경우 당연히 Timeout이 되는 알고리즘이다. 

x 좌표가 0부터 1,000,000 까지 인데, 각 위치의 모든 합(먹이 개수 MAX 100000)을매번 구한다는 생각자체가 오류다. 

거미의 이동 거리를 고려하지 않고 겨우 백 만번 연산하는데 1초이상 걸리겠어? 라고 생각한 나의 실수다. 

결국 input.txt의 각 항목 값을 MAX로 주고 프로그램을 돌리면 약 1초에 1000번 밖에 연산이 이루어지지 않는다. 

문제의 조건에 맞추기 위해서는 지금보다 1000배 빨리 연산할 수 있는 알고리즘을 만들었어야 한다. 

나는 멍청하다. 다음번에는 더 효율적인 알고리즘을 생각하도록 노력해야겠다.