[정올] 1669번: 소시지 공장

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=942&sca=50&sfl=wr_hit&stx=1669&sop=and 

JUNGOL

문제 이해

계속 DFS, BFS만 생각하다가 이 문제를 봐서 처음에 DFS를 해야하나? 생각했다.

근데 소시지가 5000개이다. 절대 불가능

 

Greedy를 사용해야 하는 문제이다.

 

공장을 한 번 정비할 때 최대한의 소시지를 만들고 다시 정비하고 최대한 만들고 정비하고... 를 반복해야 한다.

한 번 정비 후마다 남아있는 소시지 중에 가장 작은 소시지부터 만들면 된다. 

 

• 루프를 돈다. (남은 소시지 개수 > 0 까지)
  • 소시지 배열을 정렬한다. (길이를 기준으로 정렬한다. )
  • 루프를 돈다. 
    • 여기서는 자신보다 길이도 길고, 너비도 길고 넓은 것을 다 만들어버릴 것이다. 
    • 어차피 길이를 기준으로 정렬해서 길이는 항상 현재 소시지보다 기므로, 소시지의 너비를 비교한다.
    • 만약 너비가 지금 소시지보다 같거나 넓으면 소시지를 만든다. (현재 소시지값을 갱신)
    •                                       아니면 못만든다. 넘어간다. 
      • 만든 소시지는 길이와 너비를 최대로 해서 정렬할 때 뒤로 가도록 한다.   

 

작성 코드 (C)

#include <stdio.h>
#include <stdlib.h>

int N;

typedef struct sausage {
    int l;  // 길이
    int w; // 너비
}SAU;

SAU arr[5000 + 10];

int comp(const void* a, const void* b) {

    // 길이, 너비 모두 작은 순서
    SAU* p = (SAU*)a;
    SAU* q = (SAU*)b;

    if (p->l == q->l) return p->w - p->w;
    else return p->l - q->l;
}

int main(void) {

    int time = 0;
    int cnt, loop_end, sw, sl;

    // 입력
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &arr[i].l, &arr[i].w);
    }

    cnt = N;
    while (cnt > 0) {
        time++;
        qsort(arr, N, sizeof(SAU), comp);
        loop_end = cnt;
        sw = -1, sl = -1;
        for (int i = 0; i < loop_end; i++) {
            if (arr[i].w >= sw) { // 전에 만든 소시지보다 w가 더 넓으면
                sw = arr[i].w;
                sl = arr[i].l; // 현재 소시지 스펙 갱신 -> 소시지 만듦
                arr[i].l = 0x7fffffff; // 이미 만든 소시지 값 최대로해서 
                arr[i].w = 0x7fffffff; // sort 시에 맨 뒤로 가게
                cnt--;
            }
        }
    }

    printf("%d", time);
    return 0;
}