[백준 / BOJ] 6209 제자리 멀리뛰기

문제

출처 : https://www.acmicpc.net/problem/6209

6209번: 제자리 멀리뛰기

시작지점(0번)에서 각각 일정 거리 떨어진 n개의 돌섬이 있다. 

이때, n개의 돌섬중 m개를 제거하여 돌섬사이의 거리의 최솟값을 최대로 하는 문제이다.

---

풀이

문제에 나와있는 "최솟값을 최대"로 라는 키워드가 결정문제임을 알려주니 문제의 입력조건을 살펴보고 결정문제로 풀린다면 풀면 된다. 못 푼다면 DP로 풀면된다(모든 결정문제는 DP로 풀린다고함 <- 종만북).

 

이 문제도 well known 결정문제라서 그대로 풀면됐는데, 시작지점과 끝지점에 대한 처리를 해줘야 한다는 점을 주의해서 풀면 된다.

우선, 알고리즘을 살펴보자.

left = 0, right = 거리의 최댓값 일때,

-> m개의 돌 섬을 제거했을때, 각 돌섬 거리의 최솟값의 최댓값을 (left + right) / 2로 만들 수 있는가?

-> 있다면, 최솟값의 최댓값을 더 크게 하는 경우를 살펴보기 위해서, left를 mid+1로 변경한다.

-> 없다면, 최솟값의 최댓값을 더 작게 만드는 경우를 살펴보기 위해서, right를 mid-1로 변경한다.

위 과정을 left <= right를 만족할때 까지 반복하면 된다.

 

다시 주의할 점 으로 돌아가서, 다음 테스트케이스를 생각해보자.

 

10 1 0

5

답 : 5

오답 : 10

 

11 2 0

4

8

답 : 3

오답 : 4

2022.12.26 - 사실, 위 테스트 케이스는 처리하지않아도 AC가 나오는데, 테스트 케이스가 부족한것 같아서, 추가 요청을 올렸다. 실제로, 3을 출력하는 코드와 4를 출력하는 코드 모두 정답으로 인정되고 있는데, 이 테스트 케이스가 출제자가 의도한 테스트 케이스가 맞다면, 두 경우중 하나는 테케가 추가되었을때, 틀렸습니다가 나올것이다.

https://www.acmicpc.net/board/view/106222

글 읽기 - 데이터를 추가해주세요.

주요 소스코드

    private boolean isFarable(int distance){
        int currentDeleted = delete;
        int beforeIdx = 0;
        for(int i = 1; i < islands.size(); i++){
            if(islands.get(i) - beforeIdx < distance) {
                if(currentDeleted == 0) return false;
                currentDeleted--;
                continue;
            }
            beforeIdx = islands.get(i);
        }
        return true;
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/6209%20제자리%20멀리뛰기/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃