티스토리 뷰

알고리즘 관련/BOJ

BOJ)2230 수 고르기

JASON 자손9319 2017. 4. 4. 16:25

문제: icpc.me/2230


N개의 원소로 이루어진 수열에서 두 수를 뽑았을 때 그 수의 차이가 M보다 크면서 가장 작은 두 수의 차이를 구하는 문제이다.


우리는 정렬을 해준 뒤 투 포인터 i , j 를 설정하여 문제를 해결할 수 있다.


a[i]-a[j]가 m보다 작다면 두 수의 차이가 더 커져야 하므로 i를 증가시키고 m보다 크거나 같다면 j를 증가시키는 방법으로 해결해나가면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <algorithm>
#define INF 1987654321
using namespace std;
int n, m, a[100001], r;
int main() {
    scanf("%d%d"&n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d"&a[i]);
    sort(a, a + n);
    int j = 0;
    r = INF;
    for (int i = 0; i < n&&< n;) {
        if (a[i] - a[j] >= m) {
            r = min(r, a[i] - a[j]);
            j++;
        }
        else 
            i++;
    }
    printf("%d\n", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2618 경찰차  (2) 2017.04.05
BOJ)2688 줄어들지 않아  (0) 2017.04.04
BOJ)2230 수 고르기  (0) 2017.04.04
BOJ)9463 순열 그래프  (1) 2017.04.03
BOJ)2992 크면서 작은 수  (0) 2017.04.03
BOJ)1058 친구  (0) 2017.04.03
댓글
댓글쓰기 폼