[백준 #2965번 JAVA] 캥거루 세마리 풀이

📄 캥거루 세마리 [백준 2965번]

🔗 [전체 소스 코드]
🔗 [문제 풀러 가기]

---

문제 해설

문제는 단순 상황 파악만으로 해결할 수 있습니다. 먼저 문제의 조건을 살펴보며 해결방법을 알아보겠습니다.

문제 조건

1. 캥거루 세마리는 일직선 상에 서로 다른 좌표위에 있다.
2. 한 번 움직일 때 바깥쪽에 있는 두 캥거루 중 한마리가 다른 캥거루 사이의 정수 좌표로 점프한다.
3. 한 좌표 위에 캥거루가 두 마리 이상일 수는 없다.

위의 조건을 살펴보면 바깥쪽 두 캥거루 중 한마리가 다른 캥거루 사이의 정수 좌표로 점프한다고 하였습니다. 여기서 정수 좌표는 중앙이라고 표시되어 있지 않기 때문에 어떤 좌표로든지 이동할 수 있습니다. 이 점을 힌트로 삼으면 매번 바깥쪽 캥거루 중 이동시킬 한 마리를 정하지 않아도 됩니다. 이유는 다음과 같습니다.

문제에서 요구하는 것은 캥거루가 최대로 움직일 수 있는 횟수를 찾아내는 것입니다. 그렇다면 결국 바깥쪽 두 캥거루 중 가운데 캥거루와 거리가 가장 먼 캥거루 사이에 다른 캥거루가 들어온다면 최대한 많이 이동할 수 있습니다. 또한 매번 바깥쪽 캥거루 중 이동 할 캥거루를 정할 필요 없이 거리가 가장 먼 캥거루를 고정시킨 다음 남은 두 캥거루가 자리를 바꿔가며 고정된 캥거루 쪽으로 이동을 한다면 쉽게 문제를 해결할 수 있습니다. 즉, 이동해야 할 캥거루가 가운데 캥거루 바로 옆자리로 이동을 하면 최대로 많이 이동을 할 수 있게 됩니다. 그림을 보면 쉽게 이해하실 수 있습니다.

예제 1

주어진 캥거루의 좌표
3 5 9

초기 캥거루 위치 상태

위치	3	4	5	6	7	8	9
캥거루	o		o				o

위와 같이 주어져 있다면 바깥쪽 두 캥거루 중 가운데 캥거루와 거리가 가장 먼 캥거루는 9번 위치에 있는 캥거루 이므로 9번 캥거루를 고정시킵니다. 이 후 3번 캥거루를 5와 9 사이로 이동시키는데 9번이 고정되어 있으므로 3,5번 캥거루가 9번쪽으로 다가가면서 가장 많이 이동하기 위해선 가운데 캥거루의 바로 옆자리로 점프하면서 이동하는 것이 가장 많이 이동할 수 있는 방법입니다. 따라서 3번 캥거루를 6번자리로 이동시킵니다.

이동 1

위치	3	4	5	6	7	8	9
캥거루			o	o			o

이동 한 뒤 9번은 계속해서 고정된 상태가 되고 5번 위치에 있는 캥거루가 바깥쪽이 되었으므로 가운데 캥거루 바로 옆인 7번으로 이동합니다. 이러한 행동을 반복하면 됩니다.

이동 2

위치	3	4	5	6	7	8	9
캥거루				o	o		o

이동 3

위치	3	4	5	6	7	8	9
캥거루					o	o	o

이제 더이상 움직일 수 없으므로 최대 이동횟수는 총 3회 입니다. 여기서 확인해야 할 점은 이동하는 횟수를 굳이 반복문을 돌려서 확인을 해야하나? 입니다. 고정할 캥거루가 정해진다면 가운데 캥거루와 남은 캥거루가 자리를 바꿔가며 이동하는 횟수가 최대 횟수이므로 | 고정 캥거루의 위치 - 가운데 캥거루의 위치 | - 1로 답을 찾을 수 있습니다. 절댓값으로 구해야 하는 이유는 고정 캥거루의 위치가 왼쪽일 경우 음수값이 나오기 때문입니다.

예외 사항

예외사항이 존재하는데 초기 주어진 세 마리의 캥거루 위치가 모두 연속이라면 움직일 수 없으므로 0을 반환해야 합니다.

ex)
3 4 5
55 56 57
...

풀이 순서

1. 예외상황인 세 마리의 캥거루가 연속인지 확인
2. 고정시킬 캥거루를 선택
3. | 고정캥거루 위치 - 가운데 캥거루 위치 | - 1 출력

글보단 코드를 보면 더 이해하기 쉽습니다.

---

🌱 main 함수

public static void main(String[] args) throws IOException {
    String[] position = br.readLine().split(" ");
    int left = Integer.parseInt(position[0]);
    int middle = Integer.parseInt(position[1]);
    int right = Integer.parseInt(position[2]);

    System.out.println(solve(left, middle, right));
}

🌱 solve 함수

캥거루가 최대 이동할 수 있는 횟수를 구하는 함수입니다.

private static int solve(int left, int middle, int right) {
    if (middle - left == 1 && right - middle == 1) return 0;
    int pixPosition = findFixPosition(left, middle, right);

    return Math.abs(pixPosition - middle) - 1;
}

🌱 findFixPosition 함수

고정시킬 캥거루의 위치를 구하는 함수입니다.

private static int findFixPosition(int left, int middle, int right) {
    return right - middle > middle - left ? right : left;
}

---

💡 Github에 더 많은 문제 풀이가 있습니다.

Programmers 문제 풀이

BaekJoon Online Judge 문제 풀이