[C] 백준 - 1946번: 신입 사원

7월 19일(수)-그리디 알고리즘(1946번)

1946번: 신입 사원

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 문제자체에 대한 이해를 정확히 하는 것이 중요하다

- 1차 점수와 2차 점수 중 적어도 하나가 다른 지원자보다 떨어지지 않는자만 선발한다

  이는 결국 1차 점수를 이용해서 정렬을 해놓은 뒤, 해당 상황에서 2차 점수를 가지고 카운팅을 해주어야한다

 

- 한 명의 지원자에게 1차_점수와 2차_점수가 모두 존재하므로, 구조체를 이용해서 입력을 받는다

- 그리고나서 1차_점수를 qsort를 이용해서 오름차순(1등 -> 꼴등)으로 정렬해놓는다

- 1차_점수에서 1등인 지원자가 가지고 있는 2차_점수를 변수 tmp의 최초값으로 설정한 뒤,

  나머지 2등부터 꼴등까지 지원자들의 2차_점수 중에서 tmp값보다 작은 값(더 높은 등수)이 나오면

  tmp값을 갱신하고, 변수 count++를 진행한다

- 최종출력은 테스트케이스마다의 count값을 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

x

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

typedef struct{
	int first_score;
	int second_score;
}pair;

int compare(const void* a, const void* b)
{
	pair num1 = *(pair*)a;
	pair num2 = *(pair*)b;

	if (num1.first_score > num2.first_score)
	{
		return 1;
	}
	else if (num1.first_score < num2.first_score)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	int T, N;
	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		scanf("%d", &N);

		pair* person = (pair*)malloc(sizeof(pair) * N);
		for (int j = 0; j < N; j++)
		{
			scanf("%d %d", &person[j].first_score, &person[j].second_score);
		}
		qsort(person, N, sizeof(pair), compare);

		int count = 1;
		int tmp = person[0].second_score;
		for (int j = 1; j < N; j++)
		{
			if (tmp > person[j].second_score)
			{
				tmp = person[j].second_score;
				count++;
			}
		}

		printf("%d\n", count);
		free(person);
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ