[Java] BOJ 12873 기념품

12873번: 기념품

---

정답 코드

•  queue를 활용하여 해당 숫자를 외치는 사람을 queue에서 제외
• 5000^3이 int범위 초과하는 것을 생각해야함
• 나머지 연산으로 시간 복잡도 줄이기

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static int N;
    static Queue<Integer> queue;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }

        int index = 1;
        while (queue.size() != 1) {
            long pow = (long) (Math.pow(index, 3) - 1);
            long mod = pow % queue.size();

            if (mod < 0) {
                mod += queue.size();
            }

            for (int i = 0; i < mod; i++) {
                queue.add(queue.poll());
            }
            queue.poll();

            index++;
        }

        System.out.println(queue.peek());
    }
}