[GCJ] Round 1A 문제풀이

Google codejam Round 1A 문제를 풀어봤다.

주어진 v1, v2 수들에 대해 임의로 두개씩 곱한 합이 가장 작은 경우를 구하는 문제.

v1, v2를 크기로 정렬한 후에 가장 큰값과 가장 작은 값을 쌍을 지으면서 곱해서 풀면 된다.

ㅇ
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define INPUT_SIZE 100000
 
void insertion_sort(int list[], int n)
{
        int i, j, key;
        for(i=1; i<n; i++)
        {
                key = list[i];
                for(j=i-1; j >= 0 && list[j] > key; j--)
                        list[j+1] = list[j];
                list[j+1] = key;
        }
 
}
 
int main() {
 
        FILE *fp;
 
        char sLine[INPUT_SIZE];
        int loop_cnt;
        int array_size;
        int i, j, k;
        char delim[] = "' '";
        char delim_time[] = ":";
        char *token_str;
 
        //fp = fopen("small.in", "r");
        fp = fopen("large.in", "r");
 
        if(fp == NULL){
                printf("can't read file\n");
                return 0;
        }
        fgets(sLine, INPUT_SIZE, fp);
        loop_cnt = atoi(sLine);
        for( i = 0; i < loop_cnt; i++)
        {
                //파일읽기 turn around
                fgets(sLine, INPUT_SIZE, fp);
                array_size = atoi(sLine);
 
                fgets(sLine, INPUT_SIZE, fp);
                int array_x[array_size];
                int array_y[array_size];

                token_str = strtok(sLine, delim);
                for(j=0; j< array_size; j++)
                {      
                        array_x[j] = atoi(token_str);
                        token_str = strtok(NULL, delim);
                }
               
                fgets(sLine, INPUT_SIZE, fp);
                token_str = strtok(sLine, delim);
                for(j=0; j< array_size; j++)
                {      
                        array_y[j] = atoi(token_str);
                        token_str = strtok(NULL, delim);
                }
               
                insertion_sort(array_x, array_size);
                insertion_sort(array_y, array_size);
               
                double output = 0;
                for(j=0, k=array_size-1; j< array_size; j++, k--)
                {      
                        output += (double)array_x[j] * (double)array_y[k];
                }
                //printf("Case #%d: %lf\n", i+1, output);
                printf("Case #%d: %10.0lf\n", i+1, output);
        
        }      
        return 0;
}