숫자 n이 주어져 있다고 가정해 보겠습니다. 여러 명의 어린이가 원형으로 서 있으며, 시계 방향 순서대로 1부터 n까지 번호가 붙어 있고, 1번 어린이가 공을 들고 있습니다. 먼저 1번 어린이가 시계 방향으로 바로 옆 어린이(2번)에게 공을 던집니다. 그다음 2번 어린이는 한 명을 건너뛴 4번 어린이에게, 이어서 4번 어린이는 7번 어린이에게 공을 던지는 식으로 게임이 진행됩니다. 즉, 던질 때마다 이동 거리가 한 칸씩 늘어납니다. 공을 던질 때는 원의 시작점을 넘어 돌아갈 수도 있으며, 이렇게 진행하면 모든 어린이가 공을 받는 것은 아닙니다. 따라서 매번 공이 던져진 후 실제로 공을 받게 되는 어린이들의 번호를 찾아야 합니다.
예를 들어 입력이 n = 10이라면 출력은 [2, 4, 7, 1, 6, 2, 9, 7, 6]이 됩니다.
접근 방법
i번째 던지기에서는 공이 정확히 i칸 앞으로 이동한다는 규칙에 주목하면 문제를 쉽게 해결할 수 있습니다. 첫 번째 던지기에서는 1칸(1번 → 2번), 두 번째 던지기에서는 2칸(2번 → 4번), 세 번째 던지기에서는 3칸(4번 → 7번) 이동합니다. 따라서 현재 위치 p에 i를 더한 후 n으로 나눈 나머지를 구하면 다음 위치를 알 수 있습니다. 나머지가 0이 되는 경우는 원을 한 바퀴 돌았다는 의미이므로 마지막 번호인 n으로 보정합니다.
이를 위해 다음 단계를 따릅니다 −
p := 1
for initialize i := 1, when i < n, update (increase i by 1), do:
p := p + i
p := p mod n
if not p is non-zero, then:
p := n
print p
예제 코드
더 나은 이해를 돕기 위해 다음 C++ 구현을 살펴보겠습니다 −
#include <bits/stdc++.h>
using namespace std;
void solve(int n){
int p = 1;
for (int i = 1; i < n; i++){
p += i;
p %= n;
if (!p)
p = n;
printf("%d, ", p);
}
}
int main(){
int n = 10;
solve(n);
}
입력
10
출력
2, 4, 7, 1, 6, 2, 9, 7, 6,
코드 설명
변수 p는 현재 공을 가진 어린이의 번호를 나타내며 처음에 1로 초기화됩니다. 반복문 안에서 i번째 턴마다 p에 i를 더하고 n으로 모듈로 연산을 수행하여 원형 구조에서의 다음 위치를 계산합니다. 연산 결과가 0이면 원의 시작점을 지나쳤다는 의미이므로 n으로 보정해 줍니다. 이 과정을 n-1번 반복하면서 각 턴마다 공을 받는 어린이의 번호를 차례로 출력합니다. 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.