https://www.acmicpc.net/problem/12873
📌 문제
백준이는 BOJ 알고리즘 캠프 참가자 중 한 명에게 기념품을 주려고 한다. 하지만, 많은 참가자 중에서 어떤 사람을 뽑아서 기념품을 줘야하는지 고민이 되기 시작했다. 따라서, 백준이는 게임을 통해서 기념품을 받을 사람을 정하기로 결정했다.
게임이 시작하기 전에 모든 참가자 N명은 원을 이루어서 앉아있다. 다음, 1부터 N까지 번호가 적혀있는 티셔츠를 시계방향으로 입는다. 이 티셔츠는 게임에 사용되지 않으며, 게임을 쉽게 하기 위해서 입는 티셔츠이다.
게임은 단계로 이루어져 있으며, 첫 단계는 1단계이다. 각 단계가 시작될 때, 백준이는 어떤 참가자의 앞에 서있다. 그 다음, "하나"를 외친다. 그 다음, 시계 방향으로 다음 사람에게 이동하며 "둘"을 외친다. 이 과정은 t단계인 경우에 t3을 외칠 때 까지 진행한다. 예를 들어, 1단계에서는 1까지 외치며, 2단계에서는 8까지, 3단계에서는 27까지 외친다.
각 단계가 끝난 경우에, 백준이가 앞에 서 있는 사람은 게임에서 제외된다. (t단계인 경우에 t3을 외칠 때 앞에 있던 사람) 사람이 제거된 후에는 백준이는 시계 방향으로 다음 사람에게 이동한다. 1단계에서 백준이는 티셔츠 1번을 입고 있는 사람의 앞에 있다. 게임은 원에 한 명이 남을 때 까지 진행되며, 마지막 남은 사람이 기념품을 가져가게 된다.
참가자의 수 N이 주어졌을 때, 어떤 티셔츠를 입고 있는 사람이 기념품을 받는지 구하는 프로그램을 작성하시오.
⚔ 제한 사항
입력
첫째 줄에 BOJ 캠프 참가자의 수 N (1 ≤ N ≤ 5,000)이 주어진다.
출력
첫째 줄에 기념품을 받는 사람이 입고 있는 티셔츠의 번호를 출력한다.
예시
3
2
👀 문제 해석
이 문제에서 바로 떠오르는 것은 당연 원형 큐이다. 설명에서부터 원형 구조를 제시하고 있다. 참가자들이 원을 이루고 있고, 매 단계마다 특정 규칙에 따라 한 명씩 제거된다. 게임이 끝날 때까지 한 명씩 제거하다가 최후에 남는 사람이 승리하는 방식이다. 조금 더 분석해 보면, 다음과 같은 세부 사항을 확인할 수 있다.
- 참가자들은 N명이 있고, 각각 1부터 N까지 번호를 가지고 있다.
- 각 단계에서 제거될 사람은 단계에 따라 t^3번째에 해당하는 사람이 제거된다. 예를 들어, 1단계에서는 1^3 = 1번 사람, 2단계에서는 2^3 = 8번째 사람, 3단계에서는 3^3 = 27번째 사람이 제거된다.
- 문제의 핵심은 원형 구조에서 사람들이 순환하는 방식과 매 단계별로 참가자를 어떻게 효율적으로 제거할 것인가이다.
원형 큐 프로토타입과 같은 문제로 요세푸스 문제가 있다. 이 문제는 요세푸스 문제와 유사하다. 요세푸스 문제는 원형으로 앉은 사람들이 특정 규칙에 따라 제거되고 최후에 남는 사람을 구하는 문제인데, 여기서는 제거될 사람이 단계마다 다르게 결정되는 특수한 규칙이 적용된다.
🔎 접근
처음 이 문제를 봤을 때 떠오르는 방법은 가장 단순하게 원형 큐를 이용하는 것이다. 원형으로 앉은 참가자들이 시계 방향으로 순서대로 선택되며 제거되므로, 이를 그대로 구현하는 것이다. 즉, 큐를 사용해 가장 앞에 있는 사람을 선택하고, 제거된 후에는 큐의 맨 뒤로 나머지 사람을 돌려보내는 방식으로 접근할 수 있다.
이를 구현하는 방법은 매 단계에서 선택된 사람을 pop한 후, 그 다음 사람을 제거하는 과정을 반복하는 것이다. 큐에서 제거되는 사람을 poll()로 제거하고, 그 후에는 나머지 사람들을 add()하여 다시 큐에 넣어주면 된다. 이 방법은 직관적이고 단순한데, 주어지는 N=5000이므로 시간 복잡도를 한 번 따져보자.
이 방식에서의 핵심 연산은 큐에서의 pop과 add 연산이다. 각 단계마다 제거할 사람을 t^3번째로 정해야 하므로, 큐를 계속해서 순환시키며 해당하는 사람을 찾아야 한다. 참가자 수는 N이고, 단계마다 큐의 크기가 줄어들지만, 제거 대상자를 찾기 위해 t^3번만큼 큐를 순환해야 하는 상황이다.
큐의 크기가 동적으로 변하므로 시간 복잡도를 계산하기 위해서 수학적인 공식이 필요하다.
- 1단계: 큐 크기 =
N, 제거될 사람을 찾기 위해1^3 = 1번 회전 후, 첫 번째 사람을pop. - 2단계: 큐 크기 =
N-1, 제거될 사람을 찾기 위해2^3 = 8번 회전 후, 두 번째 사람을pop. - 3단계: 큐 크기 =
N-2, 제거될 사람을 찾기 위해3^3 = 27번 회전 후, 세 번째 사람을pop. - 4단계: 큐 크기 =
N-3, 제거될 사람을 찾기 위해4^3 = 64번 회전 후, 네 번째 사람을pop.
이런 식으로 큐의 크기는 점점 줄어들지만, 각 단계에서 큐의 크기에 비례하지 않고 t^3에 비례하여 회전 횟수가 증가하게 될 것이다.
최악의 경우인 N = 5000일 때, 단계별로 큐가 회전하는 횟수는 다음과 같다.
- 1단계: 큐 크기 = 5000, 회전 횟수 = 1^3 = 1
- 2단계: 큐 크기 = 4999, 회전 횟수 = 2^3 = 8
- 3단계: 큐 크기 = 4998, 회전 횟수 = 3^3 = 27
- 4단계: 큐 크기 = 4997, 회전 횟수 = 4^3 = 64
- 5단계: 큐 크기 = 4996, 회전 횟수 = 5^3 = 125
- ...
이러한 방식으로 접근하면 각 단계에서의 회전 횟수가 t³에 비례하여 증가하므로, 전체 시간 복잡도는 각 단계의 회전 횟수를 모두 합한 값이 된다. 즉, 총 연산 횟수는 다음과 같이 계산할 수 있다.
우선, 총 단계 수는 N-1이다. 참가자 N명에서 한 명이 남을 때까지 진행되므로 N-1단계가 필요하다. 각 단계에서의 회전 횟수는 t³이며, 단계 번호 t는 1부터 N-1까지 증가한다.
따라서, 총 회전 횟수는 다음의 합으로 표현된다.
\[
\text{총 회전 횟수} = \sum_{t=1}^{N-1} t^3
\]
이 합을 계산하기 위해서 수학적인 합 공식인 세제곱의 합 공식을 사용한다.
\[
\sum_{k=1}^{n} k^3 = \left( \frac{n(n+1)}{2} \right)^2
\]
이를 이용하여 \(N-1\)까지의 세제곱의 합을 구하면,
\[
\sum_{t=1}^{N-1} t^3 = \left( \frac{(N-1)N}{2} \right)^2
\]
이제 \(N = 5000\)일 때, 총 회전 횟수를 계산해 보자.
\[
\begin{align*}
\sum_{t=1}^{4999} t^3 &= \left( \frac{4999 \times 5000}{2} \right)^2 \\
&= \left( \frac{24,995,000}{2} \right)^2 \\
&= (12,497,500)^2 \\
&= 156,187,500,625,000
\end{align*}
\]
즉, 총 회전 횟수가 약 156조에 달한다. 이는 컴퓨터로 처리하기에는 너무 큰 수이며, 현실적으로 불가능한 연산량이다.
따라서, 이 알고리즘의 시간 복잡도는 \(O(N^4)\)이며,
- 각 단계에서의 연산: \(O(t^3)\)
- 단계의 수: \(N-1\)
- 총 시간 복잡도:
\[
O\left( \sum_{t=1}^{N-1} t^3 \right) = O(N^4)
\]
이렇게 큰 시간 복잡도를 가진 알고리즘은 N이 작을 때는 동작할 수 있지만, N = 5000과 같은 경우에는 당연히 시간 초과가 발생한다.
따라서, 가장 단순한 방식으로 이 문제를 해결하려고 하면 시간 내에 답을 구할 수 없다. 개선해보자.
- 모듈러 연산을 활용하기: 각 단계에서의 회전 횟수를 실제로 구현하는 대신, 수학적인 계산을 통해 직접 제거될 사람의 위치를 계산한다.
- 자료 구조의 변경: 큐를 사용하여 매번 순환하는 대신, 배열이나 연결 리스트 등을 활용하여 참가자들을 관리하고, 필요한 계산만 수행한다.
- 수학적 접근: 문제의 패턴을 분석하여 일반화된 공식을 도출하고, 이를 기반으로 답을 구한다.
📝 풀이 코드
위에서 접근한 방식으로 실제 코드 구현을 시작해보자.
1. 무식하게 풀기
가장 먼저, 첫 번째 살펴본 방식으로 문제에서 제시한 대로 큐 작동을 있는 그대로 구현하는 방법이다.
public static int 당첨자구하기(int 사람수) {
Queue<Integer> 원형큐 = new LinkedList<>();
for (int i = 1; i <= 사람수; i++) {
원형큐.add(i);
}
int 단계 = 1;
while (원형큐.size() > 1) {
int 회전횟수 = 단계 * 단계 * 단계;
for (int i = 0; i < 회전횟수 - 1; i++) {
원형큐.add(원형큐.poll());
}
원형큐.poll(); // 제거
단계++;
}
return 원형큐.peek();
}
2. 모듈러 연산으로 개선하기
핵심은 회전을 있는 그대로 해주면 안 된다는 것이다.
회전 횟수를 실제로 구현하지 않으려면 어떻게 해야할까? 원형 큐의 특성을 생각해보자.
문제의 예제 입력으로 주어진 10에 대해서, 시뮬레이션 해보자.
초기 상태에서 참가자는 1번부터 10번까지 있다.
- 참가자 리스트: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- 현재 위치 (
현재위치): 0 - 단계 (
단계): 1
첫 번째 단계를 생각해보면 단계별 횟수는 ( 1^3 = 1 ) 이다.
여기서 제거할 사람의 위치는 어떻게 구할까?
모듈러 연산을 활용하여 제거할 사람의 위치를 계산할 수 있다. 원형 큐에서는 리스트의 끝에 도달하면 다시 처음으로 돌아오므로, 이를 수학적으로 표현하기 위해 모듈러 연산을 사용한다. 이를 토대로 공식을 구해보면,
\[
\text{현재위치} = (\text{현재위치} + \text{단계별횟수} - 1) \mod \text{남은참가자수}
\]
- 현재위치: 이전 단계에서 시작한 위치. 처음에는 0으로 시작한다.
- 단계별횟수: 현재 단계에서 백준이가 외쳐야 하는 숫자의 총 개수, 즉 ( t^3 ).
- 남은참가자수: 현재 남아있는 참가자의 수.
- -1을 하는 이유: 현재 위치부터 시작하여 ( 단계별횟수 )만큼 이동하면 제거할 사람의 위치를 정확히 찾을 수 있다. 이는 현재 위치도 숫자를 세는 것에 포함되기 때문이다.
원형 큐에서 참가자들은 원을 이루고 있으므로, 인덱스가 리스트의 크기를 넘어갈 수 있다. 따라서 모듈러 연산을 통해 인덱스를 순환시키며, 리스트의 범위를 벗어나지 않도록 조정한다. 그런 뒤,현재 위치에서의 시작 을 계산해준다. 백준이는 현재 위치에 서 있는 참가자부터 숫자를 세기 시작한다. 따라서 첫 번째 숫자는 현재 위치의 참가자에게 해당된다.
여기서 왜 ( 단계별횟수 - 1 )일까? 숫자를 세는 과정에서 현재 위치의 참가자를 포함하기 때문이다. 즉, 실제로 이동해야 하는 칸 수는 ( 단계별횟수 - 1 )이다. 예를 들어, 단계별횟수가 1이면 현재 위치의 참가자가 바로 제거 대상이 된다.
각 단계별로 살펴보자.
단계 1:
- 현재위치: 0
- 단계별횟수: ( 1^3 = 1 )
- 남은참가자수: 10
- 계산:
\[
\text{현재위치} = (0 + 1 - 1) \mod 10 = 0
\]
- 제거할 사람: 인덱스 0에 위치한 1번 참가자
단계 2에서:
- 현재위치: 0 (이전 단계에서 제거 후 초기화)
- 단계별횟수: ( 2^3 = 8 )
- 남은참가자수: 9
- 계산:
\[
\text{현재위치} = (0 + 8 - 1) \mod 9 = 7
\]
직접 세어보면, 인덱스 0(2번 참가자) 앞에서 시작하여 시계 방향으로 숫자를 셀 것이므로,
- "하나" - 인덱스 0, 2번 참가자
- "둘" - 인덱스 1, 3번 참가자
- "셋" - 인덱스 2, 4번 참가자
- "넷" - 인덱스 3, 5번 참가자
- "다섯" - 인덱스 4, 6번 참가자
- "여섯" - 인덱스 5, 7번 참가자
- "일곱" - 인덱스 6, 8번 참가자
- "여덟" - 인덱스 7, 9번 참가자
백준이가 "여덟"을 외친 후, 앞에 서 있는 참가자는 9번 참가자이다. 따라서 이 참가자가 제거된다.
- 남은 참가자 리스트: [2, 3, 4, 5, 6, 7, 8, 10]
단계 3
- 현재위치: 0
- 단계별횟수: ( 3^3 = 27 )
- 남은참가자수: 8
- 계산:
\[
\text{현재위치} = (0 + 27 - 1) \mod 8 = 2
\]
이 단계에서도 마찬가지로, 다시 인덱스 0(2번 참가자) 앞에서 시작한다.
- "하나" - 인덱스 0, 2번 참가자
- "둘" - 인덱스 1, 3번 참가자
- "셋" - 인덱스 2, 4번 참가자
- "넷" - 인덱스 3, 5번 참가자
- "다섯" - 인덱스 4, 6번 참가자
- "여섯" - 인덱스 5, 7번 참가자
- "일곱" - 인덱스 6, 8번 참가자
- "여덟" - 인덱스 7, 10번 참가자
- "아홉" - 인덱스 0, 2번 참가자 (원형 큐이므로 다시 처음으로 돌아옴)
- "열" - 인덱스 1, 3번 참가자
- "열하나" - 인덱스 2, 4번 참가자
- ...
이렇게 계속해서 숫자를 세어 27번째 숫자를 외치게 된다. ( 27 - 1 = 26 )번 이동하므로, 인덱스 ( (0 + 26) \mod 8 = 2 )가 된다. 따라서 제거될 참가자는 4번 참가자이다.
- 남은 참가자 리스트: [2, 3, 5, 6, 7, 8, 10]
단계 4
- 현재위치: 0
- 단계별횟수: ( 4^3 = 64 )
- 남은참가자수: 7
- 계산:
\[
\text{현재위치} = (0 + 64 - 1) \mod 7 = 6
\]
이번에는 ( 64 - 1 = 63 )번 이동해야 한다. 참가자 수는 7명이므로 여러 바퀴를 돌게 된다.
- 이동 횟수: 63번
- 인덱스 계산:
\[
(0 + 63) \mod 7 = 6
\]
- 제거 대상: 인덱스 6, 10번 참가자
- 남은 참가자 리스트: [2, 3, 5, 6, 7, 8]
이런 식으로 각 단계마다 제거할 사람의 위치를 계산하면, 다음과 같이 요약되고, 최종적으로 단계 9에서 참가자가 한 명 남았으므로 게임이 종료된다.
| 단계 t | 단계별횟수 | 남은참가자수 | 현재위치 계산 | 제거될 사람 |
|---|---|---|---|---|
| 1 | 1 | 10 | (0 + 1 - 1) mod 10 = 0 | 1번 |
| 2 | 8 | 9 | (0 + 8 - 1) mod 9 = 7 | 9번 |
| 3 | 27 | 8 | (0 + 27 - 1) mod 8 = 2 | 4번 |
| 4 | 64 | 7 | (0 + 64 - 1) mod 7 = 6 | 10번 |
| 5 | 125 | 6 | (0 + 125 - 1) mod 6 = 2 | 5번 |
| 6 | 216 | 5 | (0 + 216 - 1) mod 5 = 0 | 2번 |
| 7 | 343 | 4 | (0 + 343 - 1) mod 4 = 2 | 7번 |
| 8 | 512 | 3 | (0 + 512 - 1) mod 3 = 1 | 6번 |
| 9 | 729 | 2 | (0 + 729 - 1) mod 2 = 0 | 3번 |
| - | - | 1 | - | 남은 사람: 8번 |
코드로 구현해보면 다음과 같다.
간단하기 때문에 바로 계산을 해줘도 되지만 고려할 변수가 2개 이상이므로 객체를 만들어서 관리해줄 수도 있다.
public static class 단계 {
private int 단계;
private long 단계별횟수;
public 단계(int 단계) {
this.단계 = 단계;
this.단계별횟수 = get단계별횟수(단계);
}
private long get단계별횟수(int 단계) {
return (long) 단계 * 단계 * 단계;
}
public void 단계별횟수차감() {
this.단계별횟수--;
}
public void 단계업() {
this.단계++;
this.단계별횟수 = get단계별횟수(단계);
}
}
이제 사람 수 입력이 주어질 때, 위의 작동을 구현하면,
private static int 당첨자구하기(int 사람수) {
ArrayDeque<Integer> 원형큐 = new ArrayDeque<>();
for (int i = 1; i <= 사람수; i++) {
원형큐.add(i);
}
long 현재위치 = 0;
단계 단계 = new 단계(1);
while (원형큐.size() > 1) {
현재위치 = (현재위치 + 단계.단계별횟수 - 1) % 원형큐.size();
// 큐에서 해당 위치만큼 이동한 후 제거 (앞으로 빼오기)
for (int i = 0; i < 현재위치; i++) {
원형큐.addLast(원형큐.removeFirst());
}
원형큐.poll();
현재위치 = 0; // 위치가 하나 줄어들었으므로 현재 위치는 0으로 리셋
단계.단계업();
}
return 원형큐.poll();
}
결국 핵심 포인트는 현재 위치를 어떻게 효율적으로 계산할 것이냐이다.
\[
\text{현재위치} = (현재위치 + 단계별횟수 - 1) \mod 남은참가자수
\]
원형 큐 특성을 이용해서 모듈려 연산을 이용할 수 있고, 결론적으로 모든 단계마다 실제 참가자들을 빼서 넣어주는 연산 대신, 딱 빼야하는 사용자 만큼만 이동하여 훨씬 효율적으로 작동할 수 있게 된다.
그렇다면 이 방식의 시간 복잡도는 어떻게 될까?
앞서 개선한 알고리즘에서 주요 연산은 다음과 같다.
- 현재위치 계산: 모듈러 연산을 통해 계산. O(1) 시간.
- 큐 회전 및 제거:
- 현재위치만큼 큐를 회전시켜 제거할 사람을 앞으로 가져옴.
- 이 과정에서 ( 현재위치 )의 크기만큼 반복문 실행.
- for (int i = 0; i < 현재위치; i++) 루프.
각 단계의 시간 복잡도는,
- 현재위치 계산: O(1)
- 큐 회전: O(현재위치)
- 단계 증가 및 준비: O(1)
현재위치는 모듈러 연산 결과로 최대 값은 남은 참가자 수에 따라 달라지므로, 즉, 현재위치는 최대 N 이다.
따라서, 총 단계 수는 ( N - 1 )단계 (참가자 수가 1명이 남을 때까지), 각 단계에서 최대 O(N) 의 시간이 걸릴 수 있으므로, 전체 시간 복잡도는 O(N^2) 이 된다.
예를 들어, N = 5000 일 때,
- 단계 수: 4999단계.
- 각 단계에서 평균적으로 N/2 만큼 큐를 회전한다고 가정하면,
- 총 연산 횟수는 \(O(N^2)\) 수준인 약 \((5000 \times 2500 = 12,500,000)\)번의 연산이 들 것이다.
문제에서 주어진 최대 시간이 2초이므로 \(O(N^2)\) 이어도 충분히 풀 수 있는 문제이다.
하지만 좀 더 개선해볼 수 없을까?
📝 풀이 코드 개선하기
개선 1: ArrayList
먼저 첫 번째로 시도할 수 있는 것은, 큐의 인덱스를 보다 직접적으로 관리하기 위해서 배열을 사용해보자는 것이다. ArrayList를 사용해보면 어떨까? ArrayList는 인덱스 기반으로 요소에 접근할 수 있으므로, 참가자의 위치를 보다 직관적으로 관리할 수 있다.
코드는 다음과 같다.
private static int 당첨자구하기(int 사람수) {
ArrayList<Integer> 참가자 = new ArrayList<>();
for (int i = 1; i <= 사람수; i++) {
참가자.add(i);
}
int 현재위치 = 0;
단계 단계 = new 단계(1);
while (참가자.size() > 1) {
현재위치 = (int)((현재위치 + 단계.단계별횟수 - 1) % 참가자.size());
참가자.remove(현재위치); // 해당 위치에 있는 참가자를 바로 제거
단계.단계업();
}
return 참가자.get(0); // 마지막 남은 참가자의 번호 반환
}
메커니즘 자체는 동일하다. 즉, 모듈러 연산을 사용하여 제거할 참가자의 인덱스를 계산하고, ArrayList의 remove(int index) 메서드를 사용하여 해당 인덱스의 참가자를 제거한다. 이후, 각 단계마다 단계를 증가시키고 마지막으로 남은 참가자의 번호를 반환한다.
마찬 가지로 예제 10으로 시뮬레이션 해보면,
- 초기 참가자 리스트: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- 현재위치: 0
- 단계: 1
단계 1:
- 단계별횟수: ( 1^3 = 1 )
- 현재위치 계산: ( (0 + 1 - 1) \mod 10 = 0 )
- 제거 대상: 인덱스 0의 1번 참가자
- 참가자 리스트 업데이트: [2, 3, 4, 5, 6, 7, 8, 9, 10]
단계 2:
- 단계별횟수: ( 2^3 = 8 )
- 현재위치 계산: ( (0 + 8 - 1) \mod 9 = 7 )
- 제거 대상: 인덱스 7의 9번 참가자
- 참가자 리스트 업데이트: [2, 3, 4, 5, 6, 7, 8, 10]
이런 식으로 진행하여 최종적으로 8번 참가자가 남게 된다.
시간 복잡도에 개선이 있었을까?
- 현재위치 계산: ( O(1) )
- 참가자 제거:
ArrayList.remove(int index)메서드는 O(N) 의 시간 복잡도를 가진다. 배열을 그대로 구현해서, 특정 인덱스의 요소를 제거하면, 그 뒤의 모든 요소를 앞으로 한 칸씩 이동시키는 작업이 포함되어 있기 때문이다.
따라서 총 단계 수 N - 1 를 고려하면 전체 시간 복잡도는 O(N^2) 이 된다.
결론적으로 ArrayList를 사용해도 전체 시간 복잡도는 O(N^2) 로 이전의 큐를 사용한 방법과 동일하다.
개선 2: LinkedList ?
- LinkedList는 요소의 추가 및 제거가 O(1) 시간에 가능하다.
- 그러나 임의의 위치로 접근하는 데 O(N) 의 시간이 필요하므로, 현재위치로 직접 이동하여 제거하는 데 시간이 많이 걸린다.
- 결론: 여전히 동일하다.
개선 3: 수학적 접근 (재귀 관계 활용)
요세푸스 문제의 메커니즘에 착안해서 재귀 관계식을 사용하는 방식이다. 사실 이 아이디어를 생각해내기가 쉽지 않다. 핵심은 문제의 패턴을 분석하여 재귀적인 관계를 찾아내는 것이다. 요세푸스의 메커니즘으로부터 생각할 수 있는 게 무엇일까? 이를 위해서, 다시 요세푸스 문제가 무엇인지 생각해보자.
요세푸스 문제란?
요세푸스 문제는 다음과 같은 고전적인 문제이다.
n명의 사람들이 원형으로 앉아 있고, 순서대로 k번째 사람을 제거한다. 마지막까지 남는 사람의 위치는 어디인가?
이 문제에서 사람들은 원형으로 배열되어 있으며, 일정한 간격으로 사람이 제거된다. 이때 마지막 남는 사람의 위치를 구하는 것이 문제의 핵심이다.
우리의 문제와의 연관성
우리의 문제에서도 사람들은 원형으로 앉아 있고, 각 단계마다 특정 규칙에 따라 한 명씩 제거된다. 하지만 요세푸스 문제와의 차이점은 제거되는 간격이 단계마다 달라진다는 것이다. 각 단계에서 제거되는 사람은 단계 t 에 따라 t^3 번째 사람이다.
재귀 관계식의 도출
요세푸스 문제에서는 재귀 관계식을 사용하여 문제를 효율적으로 해결한다. 우리의 문제에서도 이 원리를 적용할 수 있다.
요세푸스 문제의 재귀 관계식:
\[
J(n, k) = \left( J(n - 1, k) + k \right) \mod n
\]
- J(n, k) : n명의 사람이 있을 때 마지막으로 남는 사람의 위치 (0 기반 인덱스)
- k : 제거되는 간격
우리의 문제에서는 각 단계마다 제거되는 간격 k가 달라진다. 단계 t 에 따라 k = t^3 이다.
이를 토대로 우리의 문제에 맞게 재귀 관계식을 수정해보자.
재귀 관계식 수정
- f(n) : n 명의 사람이 남아 있을 때 마지막으로 남는 사람의 위치 (0 기반 인덱스)
- 단계 t : 전체 사람 수 N 에서 현재 남은 사람 수 n 을 이용하여 t = N - n + 1
- 제거되는 간격 k : t^3
따라서 재귀 관계식은 다음과 같이 표현할 수 있다.
\[
f(n) = \left( f(n - 1) + k_n \right) \mod n
\]
여기서 k_n 은 단계 t 에서의 제거 간격으로, k_n = t^3 이다.
예시를 살펴보자
N = 4 일때, 각 단계의 흐름을 살펴 보면, 초기 참가자는 [1번, 2번, 3번, 4번]에 대해서,
(1) 단계 1: t = 1 , k = 1
- 남은 참가자 수: ( n = 4 )
- 현재위치: ( f(3) = 0 ) (초기값)
- 제거할 사람의 위치:
\[
\text{위치} = (\text{현재위치} + k - 1) \mod n = (0 + 1 - 1) \mod 4 = 0
\]
- 제거되는 사람: 인덱스 0, 1번 참가자
- 남은 참가자: [2번, 3번, 4번]
- 다음 단계의 현재위치: ( 위치 = 0 )
(2) 단계 2: t = 2, k = 8
- 남은 참가자 수: ( n = 3 )
- 현재위치: ( f(2) = 0 )
- 제거할 사람의 위치:
\[
\text{위치} = (\text{현재위치} + k - 1) \mod n = (0 + 8 - 1) \mod 3 = 7 \mod 3 = 1
\]
- 제거되는 사람: 인덱스 1, 3번 참가자
- 남은 참가자: [2번, 4번]
- 다음 단계의 현재위치: ( 위치 = 1 )
(3) 단계 3: t = 3 , k = 27
- 남은 참가자 수: ( n = 2 )
- 현재위치: ( f(1) = 1 )
- 제거할 사람의 위치:
\[
\text{위치} = (\text{현재위치} + k - 1) \mod n = (1 + 27 - 1) \mod 2 = 27 \mod 2 = 1
\]
- 제거되는 사람: 인덱스 1, 4번 참가자
- 남은 참가자: [2번]
- 다음 단계의 현재위치: 위치 = 1
결론적으로 마지막으로 남은 참가자는 2번 참가자이다.
재귀식은 각 단계에서 이전 단계의 당첨자 위치에 현재 단계의 제거 간격 k 를 더하고, 남은 참가자 수 n 으로 나눈 나머지를 취하여 새로운 당첨자 위치를 결정한다.
수학적 계산이 전부이므로, 반복문 N - 1 번 실행에 대해, 각 반복마다 상수 시간 연산이므로, O(N) 의 시간 복잡도로 상당히 효율적으로 개선할 수 있다.
코드는 다음과 같다.
private static int 당첨자구하기(int 사람수) {
int 당첨자 = 0; // 초기 당첨자 위치 (0 기반 인덱싱)
for (int n = 2; n <= 사람수; n++) {
int t = 사람수 - n + 1; // 단계 번호를 1부터 사람수까지 증가
long 단계별횟수 = (long) t * t * t; // 단계별 제거 간격 k = t^3
당첨자 = (int) ((당첨자 + 단계별횟수) % n); // 재귀 관계식 적용
}
return 당첨자 + 1; // 1부터 시작하는 인덱스로 변환하여 반환
}
당첨자 위치를 0으로 설정한 뒤, 반복한다. 이때, n을 2부터 사람수까지 증가시키며, 각 단계에서 재귀 관계식을 사용하여 당첨자 위치를 업데이트한다. 최종적으로는 계산된 당첨자 위치에 1을 더하여 실제 참가자 번호를 반환한다.
구현 코드 정리
최종적으로 풀이 코드를 정리해보면 다음과 같다.
package template.Boj;
import static org.junit.jupiter.api.Assertions.*;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import org.junit.jupiter.api.Test;
public class Main {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("fundamentals/src/test/java/template/Boj/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int 사람수 = Integer.parseInt(br.readLine());
System.out.println(당첨자구하기(사람수));
}
// 원형 큐 작동 원리를 그대로 구현한 방식
private static int 당첨자구하기(int 사람수) {
ArrayDeque<Integer> 원형큐 = new ArrayDeque<>();
for (int i = 1; i <= 사람수; i++) {
원형큐.add(i);
}
단계 단계 = new 단계(1);
while (원형큐.size() > 1) {
단계.단계별횟수차감();
if (단계.단계별횟수 == 0) {
원형큐.pop();
단계.단계업();
} else {
원형큐.add(원형큐.pop());
}
}
return 원형큐.pop();
}
// 큐와 모듈러 연산을 이용한 방식
private static int 당첨자구하기(int 사람수) {
ArrayDeque<Integer> 원형큐 = new ArrayDeque<>();
for (int i = 1; i <= 사람수; i++) {
원형큐.add(i);
}
long 현재위치 = 0;
단계 단계 = new 단계(1);
while (원형큐.size() > 1) {
현재위치 = (현재위치 + 단계.단계별횟수 - 1) % 원형큐.size();
// 큐에서 해당 위치만큼 이동한 후 제거 (앞으로 빼오기)
for (int i = 0; i < 현재위치; i++) {
원형큐.addLast(원형큐.removeFirst());
}
원형큐.poll();
현재위치 = 0; // 위치가 하나 줄어들었으므로 현재 위치는 0으로 리셋
단계.단계업();
}
return 원형큐.poll();
}
// ArrayList와 모듈러 연산을 이용한 방식
private static int 당첨자구하기(int 사람수) {
ArrayList<Integer> 참가자 = new ArrayList<>();
for (int i = 1; i <= 사람수; i++) {
참가자.add(i);
}
int 현재위치 = 0;
단계 단계 = new 단계(1);
while (참가자.size() > 1) {
현재위치 = (int)((현재위치 + 단계.단계별횟수 - 1) % 참가자.size());
참가자.remove(현재위치); // 해당 위치에 있는 참가자를 바로 빼주기
단계.단계업();
}
return 참가자.get(0); // 마지막 남은 참가자의 번호 반환
}
// 요세푸스 메커니즘에 착안해 수학 + 재귀식을 이용한 방식
private static int 당첨자구하기(int 사람수) {
int 당첨자 = 0; // 초기 당첨자 위치 (0 기반 인덱싱)
for (int n = 2; n <= 사람수; n++) {
int t = 사람수 - n + 1; // 단계 번호를 1부터 사람수-1까지 증가
long 단계별횟수 = (long)t * t * t;
당첨자 = (int)((당첨자 + 단계별횟수) % n);
}
return 당첨자 + 1; // 1부터 시작하는 인덱스로 변환하여 반환
}
public static class 단계 {
private int 단계;
private long 단계별횟수;
public 단계(int 단계) {
this.단계 = 단계;
this.단계별횟수 = get단계별횟수(단계);
}
private long get단계별횟수(int 단계) {
return (long)단계 * 단계 * 단계;
}
public void 단계별횟수차감() {
this.단계별횟수--;
}
public void 단계업() {
this.단계++;
this.단계별횟수 = get단계별횟수(단계);
}
}
@Test
public void testCases() {
assertEquals(1, Main.당첨자구하기(1));
assertEquals(2, Main.당첨자구하기(2));
assertEquals(2, Main.당첨자구하기(3));
assertEquals(2, Main.당첨자구하기(4));
assertEquals(6, Main.당첨자구하기(6));
assertEquals(8, Main.당첨자구하기(10));
}
}
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 5639 이진 검색 트리 (JAVA 자바 풀이) (0) | 2024.11.23 |
|---|---|
| [백준] 앵무새 (자바 풀이 - 큐, 배열, 해시맵을 곁들인) (1) | 2024.10.12 |
| [백준] 좋은 친구 (자바 풀이) (0) | 2024.10.11 |
| [백준] 히스토그램에서 가장 큰 직사각형 (자바 풀이) (0) | 2024.10.05 |
| 백준 5397 키 로거 (JAVA 자바 풀이) (0) | 2024.01.03 |
