[정올 1669] 소시지 공장

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

JUNGOL

#include <stdio.h>

struct sausage {
	int len, wid, visited;
} ssg[5010], tmp[5010];
int N, ans;

void mergesort(int s, int e) {
	if (s >= e) return;
	int m = (s + e) / 2, k = s, a = s, b = m + 1;
	mergesort(s, m);
	mergesort(m + 1, e);
	while (a <= m && b <= e) { 
		if (ssg[a].len < ssg[b].len) tmp[k++] = ssg[a++];
		else if (ssg[a].len > ssg[b].len) tmp[k++] = ssg[b++];
		else
			if (ssg[a].wid < ssg[b].wid) tmp[k++] = ssg[a++];
			else	tmp[k++] = ssg[b++];
	}
	while (a <= m) tmp[k++] = ssg[a++];
	while (b <= e) tmp[k++] = ssg[b++];
	for (int i = s; i <= e; i++) ssg[i] = tmp[i];
}

int calc() {
	int cnt = 0;
	while (cnt < N) { //모든 소세지가 찍힐 때까지 반복
		ans++;
		int i;
		sausage curssg;
		for (i = 0; i < N; i++) if (ssg[i].visited == 0) {
			ssg[i].visited = 1;
			cnt++;
			curssg = ssg[i++];
			break;
		}//아직 안 찍힌 소세지 중 가장 작은 것 선택
		for (; i < N; i++) {
			sausage& next = ssg[i];
			if (next.visited) continue;
			if (curssg.len > next.len || curssg.wid > next.wid) continue; //건너뛰기
			else { 
				next.visited = 1; 
				cnt++;
				curssg = ssg[i];
			}
		}//위로 가면서 같이 만들 수 있는 소세지 같이 찍음
	}
	return ans;
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; i++)	scanf("%d %d", &ssg[i].len, &ssg[i].wid);

	mergesort(0, N - 1);
	ans = calc();
	printf("%d\n", ans);
	return 0;
}