[백준/BOJ]16770. The Bucket List(C) [Bronze2]

16770. The Bucket List

Farmer John is considering a change in how he allocates buckets for milking his cows. He thinks this will ultimately allow him to use a small number of total buckets, but he is not sure how many exactly. Please help him out!

Farmer John has N cows(1<=N<=100), conveniently numbered 1...N. The i th cow needs to be milked from time si to time ti, and requires bi buckets to be used during the milking process. Several cows might end up being milked at the same time; if so, they cannot use the same buckets. That is, a bucket assigned to cow i 's milking cannot be used for any other cow's milking between time si and time ti. The bucket can be used for other cows outside this window of time, of course. To simplify his job, FJ has made sure that at any given moment in time, there is at most one cow whose milking is starting or ending(that is, si 's and ti 's are all distinct).

FJ has a storage room containing buckets that are sequentially numbered with labels 1,2,3 and so on. In his current milking strategy, whenever some cow(say, cow i) starts milking (at time si ), FJ runs to the storage room and collects the bi buckets with the smallest available labels and allocates these for milking cow i .

Please determine how many total buckets FJ would need to keep in his storage room in order to milk all the cows successfully.

Input
The first line of input contains N . The next N lines each describe one cow, containing the numbers si , ti , and bi , separated by spaces. Both si and ti are integers in the range 1...1000, and bi is an integer in the range 1...10.

Output
Output a single integer telling how many total buckets FJ needs.

문제를 좀 대강 해석해보자면 FJ(Farmer John)은 N마리의 소에게서 우유를 짜는데,
각 소마다 si부터 ti까지의 시간이 걸리고, bi만큼의 양동이가 필요하다고 한다.
ti끝난 양동이는 재활용하여 사용할수있다.
입력으로 첫줄에 N마리의 소를 입력받고
그 다음줄부터 N줄까지 차례대로 젖짜는 시작시간, 끝나는시간, 필요한 양동이를 차례로 입력받는다.
출력으로는 최대로 필요한 양동이의 개수를 출력하라.

이 문제를 이틀동안 시간날때마다 고민하고 또 고민했다.
진짜 한 10번 넘게 시도했던것 같다. VS도 열어서 짜보고 했는데...
유투브에 USACO The Bucket List 검색해서 뜨는 외국인이 강의하는 풀이도 보고 대충 이해는했는데, 내가아는 언어가 아니여서......
솔직히 내가푼건아니고 구글에 다른블로그에서 도움을 진짜많이받았다.
백준에도 질문도없고, 반례도 없고 ㅠㅠ 아마도 안봤으면 절대못풀었을것이다.

code1

#include <stdio.h>
int main()
{
    int N,i,j,using_bucket=0,used_bucket=0,total_bucket=0;
    scanf("%d",&N);
    int s[100]={0},t[100]={0},b[100]={0};
    for(i=0;i<N;i++)
        scanf("%d %d %d",&s[i],&t[i],&b[i]);
    for(i=0;i<24;i++)
    {
        for(j=0;j<N;j++)
        {
            if(s[j]==i)
            {
                using_bucket = b[j]-used_bucket;
                total_bucket+=using_bucket;
            }
            if(t[j]==i)
            {
                used_bucket = using_bucket;
                using_bucket-=b[j];
            }
        }
    }
    printf("%d",total_bucket);
    return 0;
}

처음에 짠 코드다. 재활용이 가능하다는거에 꽂혀가지고,
사용중인 양동이, 사용한양동이, 양동이 총갯수를 나눠서 구해서 할라고했는데,
양동이가 쌓이면 using_bucket에 시간대별로 뺄수가 없었다.

code2

#include <stdio.h>
int main()
{
    int N, i, j,max =  0 , total_bucket = 0;
    scanf("%d", &N);
    int s[1000] = { 0 }, t[1000] = { 0 }, b[1000] = { 0 };
    for (i = 0; i < N; i++)
        scanf("%d %d %d", &s[i], &t[i], &b[i]);
    for (i = 0; i < 24; i++)
        for (j = 0; j < N; j++)
        {
            if (s[j] == i)
                total_bucket += b[j];
            else if (t[j] == i)
                total_bucket -= b[j];
            if (total_bucket >= max)
                max = total_bucket;
        }
    printf("%d", max);
    return 0;
}

두번째 짠 코드다. 사용중인 사용한 등등 나누지말고 양동이를 가장 많이쓴 시간대를 구하기만 하면 된다는것을 깨달았다. 그리고 for문에서 24까지 돌게 되어있는데, 나는 당연히 시간이니까 24시간 기준일거라 생각하고 짠건데 전혀 필요가없었다.
Both si and ti are integers in the range 1...1000, 라고 문제에 나와있었기 때문이다.

code3

#include <stdio.h>
int main()
{
    int N, i, j, max = 0, big = 0, total_bucket = 0, s, t, b;
    scanf("%d", &N);
    int bucket[1001][1001] = { 0 };
    for (i = 0; i < N; i++)
    {
        scanf("%d %d %d", &s, &t, &b);
        if (max < t)
            max = t;
        for (j = s; j <= t; j++)
            bucket[i][j] = b;
    }
    for (i = 0; i < max; i++)
    {
        total_bucket = 0;
        for (j = 0; j < N; j++)
            total_bucket += bucket[j][i];
        if (big < total_bucket)
            big = total_bucket;
    }
    printf("%d", big);
    return 0;
}

마지막(사실 더많은데..)으로 짠코드이다.
드디어 정답이 떳다..!
bucket배열을 [100][100]으로했는데, 계속 런타임에러가 났다. 그래서 나는 오버플로우가 나는줄알고 배열길이를 줄일려고 했는데, 그게아니고 예제중에 1000개가 넘는 예제가 있었는것 같다. (Outofbound) 나는 그냥 for문돌면서 총갯수구하고, 그중에 최댓값을 구하면 되는건줄 알았는데, 코드를 저렇게 짜야하는건지 몰랐다. (사실 뭐가 다른건지 모르겠다.)
다음은 이해하기위해서 그림판으로 그린그림이다.

보기엔 이래도 문제를 이해하고있다면 꽤 설명이 잘 된 그림이다.
진짜 이거풀라고 며칠동안 헤맸던게 싹풀리면서도, 찝찝한 느낌이다.....
진짜 찝찝하다...

그나저나 오늘 학원에서 파이썬공부를 좀 했다.
처음 해봤는데, C에 익숙해져있는상태라그런가 자료형 선언안해주는것도 그렇고 중괄호 안치는것도 그렇고 print를 나도모르게 printf로 쓰고있고 ㅋㅋㅋㅋ
그래도 한시간정도 하니까 점점 익숙해지더라 재밌었다 나중에 파이썬도 다뤄봐야지