[백준 / BOJ] 1242 소풍 (Java)

문제

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

1242번: 소풍

소풍을간 사람의 수 N

제거될 사람의 번호 K

동호의 번호 M 이 주어진다.

 

사람들이 원형으로 둘러앉아 순서대로 번호를 외칠때, K를 외친사람이 탈락하고, 이후 남은사람들끼리 다시 게임을 시작한다.

 

동호는 자신이 몇번째에 탈락할지 궁금하다.

동호가 몇번째에 탈락하는지 구하는 프로그램을 만들자.

 

---

풀이

어려웠던 문제다.

처음에는 현재 제거될 사람의 위치를 구하기위해 유니온파인드를 사용해서 경로를 압축해줄려했다. 

예를들어, 

1 2 3 4 5에서 2번, 3번이 이미 제거되었다면, par[2] = 4 par[3] = 4 처럼 연결해 2와 3이 참조되었을때, 바로 4번으로 연결시켜준다.

대체로 O(1)만에 찾을수있겠지만 최악의경우 O(N*N)이 걸린다. 

결국 질문게시판에서 힌트를 얻고 풀었다.

 

로직은 다음과 같다.

중요한건 "동호가 현재 게임에서 몇번째로 번호를 외치는가" 이다.

 

(동호가 번호를 외치는 위치는 파랑색 제거되는사람은 빨간색 으로 표시하겠다.)

5 2 3 을 예로들어보자

처음 게임에 임하는 사람을 세워보면 다음과 같다.

1 2 3 4 5

이때, 동호는 3번으로 외친다.

이제, 2번이 제거되면, 동호는 다음 게임에서 1번으로 번호를 외친다.

1 2 3 4

이제 2번이 제거되면, 동호는 다음 게임에서 3번으로 번호를 외친다.

1 2 3 

이 과정을 동호가 제거되는사람이 될때까지 반복하면된다.

 

동호가 외치는 번호가 변경되는 규칙을 구해보자. (이 식 유추하는게 굉장히 오래걸렸다.)

우선, 모든 번호들이 변경되는 규칙을 크게 생각해보자.

현재 제거되는 사람이 외치는 번호가 exitNumber라고 할때,

다른 사람은 다음 게임에서, (현재 자신이 외치는 숫자 - exitNumber)만큼 줄어든 숫자를 외친다. 

(exitNumber이후부터, 1, 2, 3, 4 ....순서로 외칠것이므로..위 규칙은 당연히 성립되는걸 알수있다.)

따라서, 동호가 외치는 번호는 현재 게임에서 동호가 외치는 숫자를 target이라 했을때,

(target - exitNumber)

 

위 규칙대로 동호의 위치를 구하는데, 문제가 되는것은 동호의 위치가 제거되는사람보다 뒤에있을때 이다.

1 2 3 4

를 보자.

동호의 위치는 1, 제거되는 사람은 2이다.

이때, 위 식에 그대로 대입하면, 1 - 2 = -1 이 된다. 이 때문에, 동호의 위치 < 제거되는사람 일 경우의 식을 새로 구해야했다.

 

직관적으로 생각해보면, 쉽게 유추할수있다. (근데 직관적으로 생각하는게 어렵다)

현재 제거되는 사람의 뒤로 다시 처음부터 번호를 부르기 전까지 몇명의 사람이 있을지 생각해보자.

위의 예시,

1 2 3 4

에서는 제거되는사람 뒤로 3,4 총 두명의 사람이 있다.

즉, 한바퀴 돌기 전까지 3, 4 두명의 사람이 다음게임에서 1 2 번호를 외치는것이다.

이를 식으로 나타내면 다음과 같다.

현재 사람을 numberOfPeople이라 했을때, 처음부터 번호를 부르기 전까지 거쳐야하는 사람의 수 

(numberOfPeople  - exitNumber)

가 된다. (numberOfPeople  - exitNumber) 만큼이 지난후 처음부터 시작하므로, 동호가 외치는 숫자는

(numberOfPeople  - exitNumber) + target

이 되는것이다.

따라서 최종 식은 다음과 같이 구해진다.

    private int getExit(int numberOfPeople, int target){
        int exitNumber = input[1] % numberOfPeople;
        if(exitNumber == 0) exitNumber = numberOfPeople;
        if(exitNumber == target || numberOfPeople == 1) return 1;
        if(target < exitNumber) {
            target = (numberOfPeople-exitNumber) + target;
        }
        else target = target - exitNumber;
        return 1 + getExit(numberOfPeople-1,target);
    }

input[0] = N, input[1] = K, input[2] = M 이다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1242%20%EC%86%8C%ED%92%8D/Main.java

devxb/JJUNalgo