반응형
https://www.acmicpc.net/problem/1449
1449번: 수리공 항승
첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나
www.acmicpc.net
코드를 보기전에: 나는 이 문제를 오름차순과 반복문을 사용해 풀었다.
물이 새는곳의 개수와 테이프의 길이를 입력받는다.
그리고 물이 새는곳의 위치를 입력받아야 한다.
|
1
2
3
4
5
6
7
|
int N, L;
int cnd = 0;
scanf("%d %d", &N, &L);
for (int a = 0; a < N; a++)
{
scanf("%d", &leak[a]);
}
|
cs |
입력을 받은 뒤, 오름차순으로 숫자를 정리해야 물이 새는곳의 간격이 최소가 돼서 오름차순으로 정리해준다.
https://solution-is-here.tistory.com/30?category=979031
C언어 qsort 함수 (C언어 C11 C99)
정렬문제를 풀때는 보통 이중 반복문으로 쉽게 풀수 있으나, 배열의 크기와 숫자가 커지면 시간초과가 나온다. 그럴때는 qsort함수를 사용하면 된다. qsort함수는 퀵 정렬 함수라고도 불린다. stdlib
solution-is-here.tistory.com
qsort 함수 정렬을 이용해 오름차순으로 정리했다.
문제에서 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 한다고 했으므로, 한번에 (테이프의 길이)L -1만큼 덮는다.
|
1
2
3
4
5
6
7
8
9
|
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++;
}
}
|
cs |
반복문에서 B가 (테이프의 길이)L에서 1을 뺀 만큼까지 증가하므로, 테이프의 길이에서 1을 뺀만큼 덮게 된다.
cnd는 테이프의 개수다.
Full Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#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);
}
|
cs |
반응형