영훈이가 소시지 공장에 견학을 갔다. 그 소시지공장에서는 하나의 기계가 길이와 너비가 다양한 소시지를 만들어 내고 있었다.
유심히 살펴보니 그 기계는 현재 만들고 있는 소시지의 길이와 너비가 바로 전에 만들었던 소시지의 길이, 너비보다 크거나 같아야만 기계가 쉬지 않고 작동하고 있었다. 만약 현재 만들고 있는 소시지의 길이 또는 너비가 바로 전에 만든 것보다 작다면, 기계가 준비 작업을 하는데 1분이 소요된다는 것을 알았다.
영훈이는 주문 받은 소시지의 길이와 너비를 보고 어떤 소시지부터 만들어 나가는 것이 기계의 준비 작업에 소요되는 시간을 줄일 수 있을지 고민하고 있다.
주문받은 소시지들을 만드는데 기계가 준비 작업에 소요한 최소의 시간을 구하는 프로그램을 작성하시오.
단, 첫 소시지를 만들 때는 기계의 준비작업 시간이 1분 소요된다.
첫 줄에는 주문받은 소시지의 개수 N(1≤N≤5,000)이다.
둘째 줄에는 소시지의 길이 SL과 소시지의 너비 SW가 N개의 쌍으로 나열된다. (1 <= SL, SW <= 10,000)
주문받은 소시지들을 만드는데 기계가 준비 작업에 소요한 최소의 시간을 출력한다.
 5
4 9 5 2 2 1 3 5 1 4 |  2 |
 3
1 3 2 2 3 1 |  3 |
Code
#include <stdio.h>
#pragma warning(disable:4996)
//소세지 구조체 생성
typedef struct ham{
int length;
int area;
}st_ham;
int main(){
int score = 0;
st_ham ham[5000];
bool ham3[5000] = { 0, };
int T_case;
int i, j;
int temp;
//test 갯수 입력
scanf("%d", &T_case);
//길이 넓이 입력
for (i = 0; i < T_case; i++){
scanf("%d %d", &ham[i].length, &ham[i].area);
}
//길이로 정렬
for (j = 0; j < T_case - 1; j++){
for (i = 0; i < T_case - 1 - j; i++){
if (ham[i].length>ham[i + 1].length){
st_ham temp;
temp = ham[i];
ham[i] = ham[i + 1];
ham[i + 1] = temp;
}
else if (ham[i].length == ham[i + 1].length){
if (ham[i].area>ham[i + 1].area){
st_ham temp;
temp = ham[i];
ham[i] = ham[i + 1];
ham[i + 1] = temp;
}
}
}
}
//길이로 정렬후 너비를 정렬 했을때 걸리는 최소시간
for (j = 0; j < T_case-1; j++){
if (ham3[j] == false){
temp = ham[j].area;
ham3[j] = true;
score++;
}
for (i = 0; i < T_case - 1; i++){
if (temp <= ham[i + 1].area && ham3[i + 1] == false){
temp = ham[i + 1].area;
ham3[i + 1] = true;
}
}
}
//점수 출력
printf("%d\n", score);
return 0;
}
