흔한 개발자 이야기

/*
ID: ****
LANG: C
TASK: barn1
*/

/*#define __DEBUG__*/
#define MAXSTALL1 200+1

#include <stdio.h>

int main()
{
    int max, stal, cow;
    int i, temp;
    int before = 0;
    int total = 0;
    int ival[MAXSTALL1];
    int status[MAXSTALL1];
   
    for(i=0 ; i<MAXSTALL1 ; i++)
    {
        ival[i] = 0;
        status[i] = 0;
    }
   
#ifndef __DEBUG__
    FILE *fin;
    FILE *fout;
   
    fin = fopen("barn1.in","r");
    fout = fopen("barn1.out","w");
    fscanf(fin,"%d %d %d",&max,&stal,&cow);
#else
    printf("Input max & stall & cow : ");
    scanf("%d %d %d",&max,&stal,&cow);
#endif
   
    for(i=0 ; i<cow ; i++)
    {
#ifndef __DEBUG__
        fscanf(fin,"%d",&temp);
#else
        scanf("%d",&temp);
#endif
        status[temp] = 1;
    }
   
    for(i=0 ; i<=stal ; i++)
    {
        if(status[i] == 1)
        {
            if(before != 0)
                ival[i-before-1]++;
            before = i;
        }
    }
   
    max--;
    for(i=stal ; i>0 ; i--)
    {
        if(max > 0)
        {
            if(ival[i] >= max)
            {
                total += (ival[i] - max)*i;
                max = 0;
            }
            else
                max -= ival[i];
        }
        else
            total += ival[i]*i;
    }
#ifndef __DEBUG__
    fprintf(fout,"%dn",total+cow);
    fclose(fin);
    fclose(fout);
#else
    printf("%dn",total+cow);
#endif
    return 0;
}

저번 문제와 비슷한 접근 방법으로 문제를 해결했다.

주어진 갯수의 널판지로 최소한의 길이의 널판지를 이용해서 헛간을 고치겠다는 것이 문제였다. 비어있는 칸은 반드시 고칠 필요가 없고, 소가 있는 칸만 고치면 되므로, 소가 있는 칸 사이의 넓이가 가장 넓은 곳 부터 비우는 방식으로 널판지 갯수를 맞췄다.

소가 있는 칸 번호가 반드시 순서대로 들어오는 것은 아니므로 연산이 더 필요했다.