#12873 : 기념품

풀이방법

사용된 것:

Deque

 

2022.08.02

덱을 만들고, 원형인 것처럼 작동하게 하면 된다.

 

덱을 만들어서 1부터 N까지의 정수를 넣어두면 준비 끝이다.

 

이제 문제의 상황을 시뮬레이션하면 된다.

 

백준이가 숫자만 외치고 그냥 다음 사람으로 넘어가는 것은, 덱의 첫 요소를 꺼내서 가장 뒷 순서로 보내는 것과 같다.

deque.add(deque.poll());

이렇게 하면 된다.

 

그러므로

for(int t=1; t<N-1; t++){
	for(int i=0; i<Math.pow(t, 3)-1; i++){
    	deque.add(deque.poll());	//숫자만 부르고 넘어가기
    }
    deque.poll();	//한 명 제거하기
}

이렇게 짜주면 완벽한 시뮬레이션이 될 것이다.

 

그러나!

이렇게 했다가는 시간초과가 날 것이 안 봐도 뻔하다.

N의 최댓값이 5000이기 때문이다.

 

mod 연산을 이용하면 횟수를 크게 줄일 수 있다.

(t의 세제곱을 현재 남은 사람 수로 나눈 나머지)번째 사람을 제거하면

(t의 세제곱)번째 사람을 제거하는 것과 동일한 효과를 얻을 수 있다.

나머지가 0일 때에는 덱의 가장 마지막에 있는 요소를 제거하면 된다.

 

 

코드

Java(2022.08.02)

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc= new Scanner(System.in);
		
		Deque<Integer> people = new LinkedList<Integer>();
		
		int n = sc.nextInt();
		//1부터 N까지의 수를 덱에 넣기
		for(int i=1; i<n+1; i++) people.add(i);
		
		int t = 1;
		while(people.size() != 1) {
			//제거될 사람이 몇 번째 사람인지 구하기
			long powed = (long)Math.pow(t, 3);
			int delete = (int)(powed % people.size());
			
			//delete가 0이라면 마지막 사람을 제거
			if(delete==0) people.pollLast();
			
			else {
				//delete-1 번 제끼기
				for(int i=0; i<delete-1; i++) people.add(people.poll());
				//가장 앞의 사람 제거
				people.poll();
			}
			
			t++;
		}
		
		//정답 출력
		System.out.print(people.poll());
		
		sc.close();

	}

}