문제
동호와 동호네 반 친구들은 산정호수로 소풍을 갔다. 총 N명이 소풍에 참가했고, KIN 게임을 하려고 한다. 이 게임은 다음과 같이 진행된다.
무대에 올라간 N명은 1번부터 N번까지 시계방향으로 원형으로 앉았다. 이 게임은 1번부터 시작된다. 그리고 한 명씩 시계방향으로 1, 2, ... , K까지 센다. K를 말하는 사람은 퇴장 당한다. 그 후에는 다음 자리에 앉아있는 사람이 1부터 다시 센다. 동호도 이 게임에 M번 학생으로 참가한다. 동호는 자기가 몇 번째로 퇴장 당하는지 궁금해졌다.
예를 들어, 5명의 학생이 참가하고 K=2이고, 동호는 3번 학생이라고 하면, 가장 처음에는 1 2 3 4 5와 같이 앉아있다. 1부터 게임을 시작하기 때문에, 1이 1이라고 말하고, 2가 2라고 말한다. 2가 퇴장 당한다. 3이 1이라고 말하고, 4가 2라고 말한다. 4가 퇴장 당한다. 그 다음에는 1이 퇴장 당한다. 그 후에는 5가 퇴장당하고, 마지막으로 3이 퇴장 당한다. 동호는 3번 학생이기 때문에, 5번째로 퇴장 당한다.
N, K, M가 주어졌을 때, 동호가 몇 번째로 퇴장 당하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 N, K, M가 주어진다.
출력
첫째 줄에 동호가 몇 번째로 퇴장당하는 지 출력한다.
제한
- 1 ≤ N, M ≤ 5,000,000
- 1 ≤ K ≤ N
접근 방법
-
N개의 시계방향을 그려내야 할 것 같습니다. 처음 떠올린 방식은 큐를 사용해서 있는 그대로 구현하는 방식입니다. 하지만 문제를 읽어보니 N이 5,000,000 입니다. 다시 말해, 큐로 한 판마다 퇴장 당하는 경우를 구현하면 최악의 경우 O(NK) 의 효율을 갖게 됩니다. (약 500만^2 = 25조)
-
조금 더 효율적인 방식을 생각해 봅시다. 시각을 바꾸어 매 판마다 굳이 모든 학생을 염두하지 않고 동호의 위치만 추적해 보는겁니다.
-
동호의 상태는 크게 두 가지 경우로 나뉩니다. (1) 1번부터 시작해서 K번까지 동호가 말하지 않는 경우 와 (2)1번부터 K번 사이에 동호가 번호를 말하는 경우 입니다.
-
(1)의 경우 동호의 다음 게임에서의 순서는 (현재 동호의 순서 - 탈락자의 순서)입니다.
-
(2)의 경우 동호의 다음 게임에서의 순서는 (현재 게임 참여 인원 - 탈락자의 순서 + 현재 동호의 순서)입니다.
-
동호의 순서가 탈락자의 순서와 같을 경우 우리는 해당 게임에서 동호가 탈락함을 알 수 있습니다.
⚠️주의할 점⚠️
- 수학, 정수론 문제들은 대부분 접근 방식을 알 때와 모를 때의 난이도가 굉장히 많이 차이가 납니다. 해당 알고리즘에 익숙하지 않다면 먼저 자료구조를 떠올려보고 문제에 맞게 최적화 해보시는 것도 도움이 됩니다.
- while 문의 조건을 보면 m % n 조건이 있습니다. input = (2 4 2) or (2 2 2)와 같은 경우의 처리를 위한 요건입니다. 문제를 풀다보면 놓치기 쉬우므로 조심해야 합니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Picnic {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int k = Integer.parseInt(input[1]);
int m = Integer.parseInt(input[2]);
int cnt = 1;
int removed;
while ((removed = k % n) != m % n) {
if (removed < m) {
m -= removed;
} else {
m = n - removed + m;
}
n--;
cnt++;
}
System.out.println(cnt);
}
}결과
