[C] 백준 - 1449번: 수리공 항승

8월 30일(수) - 그리디 알고리즘 (1449번)

1449번: 수리공 항승

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

 

최초 생각 정리

- 입력은 물이 새는 곳의 개수로 N과 테이프의 길이인 L, 그리고 N개의 물이 새는 곳의 위치이다

- 예제 3번을 통해서 제공되는 N개의 물이 새는 곳의 위치가 정렬되지 않은 상태라는 것을 알 수 있다

  따라서 leak_point[ ]에 입력받은 이후, qsort를 통해서 오름차순으로 정렬한다

- 그리고 변수 start에다가 leak_point[ 0 ]값을 넣어놓은 뒤

  start와 leak_point[ ]의 차이가 L보다 작은 경우에는, 기존의 테이프를 그대로 사용할 수 있고

  start와 leak_point[ ]의 차이가 L보다 크거나 같은 경우에는, 새로운 테이프를 하나 더 써야한다

- 출력은 변수 tape를 출력한다

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

 

문제점

int main(void)
{
	
    	...

	qsort(leak_point, N, sizeof(int), compare);

	int tape = 1;
	int start = leak_point[0];
	for (int i = 1; i < N; i++)
	{
		if (leak_point[i] - start < L)
		{
			continue;
		}
		else
		{
			tape++;
			start = leak_point[i]; // <추가>
		}
	}
    
    	...

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

1. leak_point[ i ] - start 가 L보다 크거나 같은 경우, 새로운 테이프를 하나 더 써야한다

-> 이때 tape++만 해주고, start값을 새롭게 갱신해주지 않아서 처음에 이상한 값이 출력되었다

-> start = leak_point[ i ]를 추가해주며 해결

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

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int leak_point[1001];

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

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

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

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &leak_point[i]);
	}

	qsort(leak_point, N, sizeof(int), compare);

	int tape = 1;
	int start = leak_point[0];
	for (int i = 1; i < N; i++)
	{
		if (leak_point[i] - start < L)
		{
			continue;
		}
		else
		{
			tape++;
			start = leak_point[i];
		}
	}

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

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