[백준 1242번] 소풍

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

 

문제 유형

• 수학

 

문제 난이도

• Gold 1

 

문제 분석

총 N명 학생에 대하여 순서대로 번호를 부르고, K번을 부른 사람을 퇴장시킨다. 퇴장한 사람 다음 사람이 다시 1번부터 차례대로 숫자를 불러 K번 부르는 사람을 퇴장하도록 반복하고, M번에 해당하는 사람이 퇴장할 때 몇 번째로 퇴장하는지를 구하는 문제이다.

문제에서 N <= 5,000,000라고 주어졌고, 단순하게 생각한다면
시간 복잡도는 O(N*K)로 N번 순회하면서 그때의 K번째 사람을 찾아서 제외한다면 시간 초과가 발생한다.

따라서 시간 복잡도를 줄이는 문제였다.
 
숫자는 1번부터 시작하지만 인덱스를 0번부터 시작한다고 가정했을 때, 처음 M번에 해당하는 사람은 (M-1) 번째에 위치하고, 처음 시작은 1번부터 시작하므로 0번 인덱스부터 시작한다.

K번 부른 사람을 제거하고, 바로 다음 사람부터 다시 시작한다고 했을 때, 사람은 계속 한 명씩 줄어들 것이고,
이전 인덱스 + (K-1) 번째에 해당하는 사람이 다음 번에 제거 될 것이다. 원형으로 사람들이 둘러쌓여 있으므로, 전체 인원수에 대한 mod를 통해 인덱스를 찾아낼 수 있다.

 

전체 코드

package _250601;

import java.util.*;
import java.io.*;
/**
 *packageName    : _250601
 * fileName       : BOJ_G1_1242_소풍
 * author         : moongi
 * date           : 6/1/25
 * description    :
 *
 */
public class BOJ_G1_1242_소풍 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int pos = M - 1;

		int prev = 0;
		int cnt = 0;

		for (int i = N; i > 0; i--) {

			int idx = (prev + (K - 1)) % i;
			cnt++;

			if (pos == idx) {
				sb.append(cnt);
				System.out.println(sb);
				return;
			}

			if (idx < pos) {
				pos--;
			}

			prev = idx;
		}
	}
}