[BOJ] 12873. 기념품 (🥈, 큐)

🔗

풀이

처음 백준이가 서 있는 위치를 idx 라고 하자. 여기서 t^3 만큼 이동해야 한다. 이때 한 줄로 서 있고 가장 끝까지 이동하면 다시 처음으로 되돌아오는 구조이기 때문에 t^3을 전체 서 있는 사람의 수로 나눈 나머지가 실제 중복 없이 이동해야 하는 거리이다. 현재 서 있는 위치도 포함해야 하기 때문에 전체 이동해야 하는 거리에서 1을 빼주어야 한다. 단계별로 출발하는 위치는 이전 단계에서 마지막으로 위치했던 곳이므로 이전의 idx 값을 이동해야 하는 거리에 더해줘야 한다.

최대 N이 5000이기 때문에 int의 범위를 넘어서게 된다. 오버플로우가 일어나기 때문에 계속 double 로 계산하다가 마지막에 얻어지는 나머지 값을 int로 변환한다. 해당 인덱스에 위치한 사람을 제거하면 된다.

자바의 경우 list에서 remove(int n) 이면 n 인덱스에 위치한 값 제거

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(i + 1);
        }

        int t = 1;
        int idx = 0;
        while (list.size() > 1) {
            idx = (int) ((idx + Math.pow(t, 3) - 1) % list.size());
            list.remove(idx);
            t++;
        }

        System.out.println(list.get(0));
    }
}