백준(S3) 1449번: 수리공 항승 (C언어)

https://www.acmicpc.net/problem/1449

1449번: 수리공 항승

 

코드를 보기전에: 나는 이 문제를 오름차순과 반복문을 사용해 풀었다.

물이 새는곳의 개수와 테이프의 길이를 입력받는다.

그리고 물이 새는곳의 위치를 입력받아야 한다.

 

int N, L;
    int cnd = 0;
    scanf("%d %d", &N, &L);
    for (int a = 0; a < N; a++)
    {
        scanf("%d", &leak[a]);
    }

입력을 받은 뒤, 오름차순으로 숫자를 정리해야 물이 새는곳의 간격이 최소가 돼서 오름차순으로 정리해준다.

https://solution-is-here.tistory.com/30?category=979031 

C언어 qsort 함수 (C언어 C11 C99)

qsort 함수 정렬을 이용해 오름차순으로 정리했다.

 

문제에서 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 한다고 했으므로, 한번에 (테이프의 길이)L -1만큼 덮는다.

 

for (int a = 0; a < N; a++)
    {
        if (tape[leak[a]] == 0)
        {
            for (int b = 0; b < L; b++)
                tape[leak[a] + b] = 1;
            cnd++;
        }
    }

반복문에서 B가 (테이프의 길이)L에서 1을 뺀 만큼까지 증가하므로, 테이프의 길이에서 1을 뺀만큼 덮게 된다.

cnd는 테이프의 개수다.

 

Full Code

#include <stdio.h>
#include <stdlib.h>
int leak[1001];
int tape[1001];
int compare(const void *a, const void *b)
{
    int num1 = *(int *)a;
    int num2 = *(int *)b;
    if (num1 < num2)
        return -1;
    if (num1 > num2)
        return 1;
    return 0;
}
int main()
{
    int N, L;
    int cnd = 0;
    scanf("%d %d", &N, &L);
    for (int a = 0; a < N; a++)
    {
        scanf("%d", &leak[a]);
    }
    qsort(leak, N, 4, compare);
    for (int a = 0; a < N; a++)
    {
        if (tape[leak[a]] == 0)
        {
            for (int b = 0; b < L; b++)
                tape[leak[a] + b] = 1;
            cnd++;
        }
    }
    printf("%d\n", cnd);
}