BOJ#7676 Saruman's Army

BOJ#7676 Saruman's Army

* 문제

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

(University > Stanford Local ACM Programming Contest > SLPC 2006 1번)

* 풀이

palantir를 가장 적게 배치하는 것이 목적이다.

문제에서 주어진 R은 반경이다.(반지름)

1. palantir 범위에 포함되지 않은 가장 왼쪽 점을 포함하는 가장 오른쪽 점을 구하자. 

  (두 점이 같을 수도 있다.)

2. 구한 오른쪽 점이 palantir 위치이다.

3. palantir 위치를 기준으로 palantir 범위에 포함되지 않은 가장 오른쪽 점을 구하자.

위 알고리즘을 모든 점이 palantir 범위에 포함될 때까지 반복한다.

,

풀이는 위와 같고,

중요한 것은 이 문제를 접했을 때 Greedy 알고리즘을 생각할 수 있느냐인 것이다.

 

1) 모든 점은 palantir 범위에 포함되어야 한다.

2) 가장 왼쪽에 있는 점은 palantir 범위에 포함되어야 한다.

3) palantir는 최소한 적게 배치해야 한다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%237676_SarumansArmy/src

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * BOJ#7676 Saruman's Army
 * https://www.acmicpc.net/problem/7676
 */

public class Main {

    public static void main(String[] args) throws IOException {

        int R = 0; // The maximum effective range of all palantirs (where 0 <= R <= 1000)
        int N = 0; // The number of troops in saruman's army (where 1 <= N <= 1000)
        int[] X; // The positions of x1, . . ., xn of each troop (where 0 ≤ xi ≤ 1000)

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // main loop
        while (true) {

            // input
            StringTokenizer st = new StringTokenizer(br.readLine());

            R = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());

            // exit
            if (R == -1 & N == -1) {

                break;
            }

            X = new int[N];

            st = new StringTokenizer(br.readLine());

            for (int i = 0; i < N; i++) {

                X[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(X);

            solve(R, N, X);

        }

    }

    static void solve(int R, int N, int[] X) {

        int i = 0;
        int ans = 0;

        while (i < N) {

            // s : 커버되지 않은 가장 왼쪽 점의 위치
            int s = X[i];

            // s(가장 왼쪽 점)으로부터 거리 R을 초과하는 점까지 진행
            while (i < N && X[i] <= s + R) {

                i++;
            }

            // p : palantir 위치
            int p = X[i - 1];
            // p(palantir 위치)으로부터 거리 R을 초과하는 점까지 진행 (palantir 영향력 밖에 있는 가장 왼쪽점을 구한다.)
            while (i < N && X[i] <= p + R) {

                i++;
            }

            ans++;
        }

        System.out.println(ans);
    }
}