[자바] 백준 12873 - 기념품 (boj java)

문제 : boj12873

 

  리스트를 하나 두고 미리 1부터 N까지를 순서대로 넣어놔보자. 그럼 이제 단계를 A라고 할 때, 1단계부터 N-1단계까지 A^3번을 리스트 순회하다가 해당 횟수에서 제외시키는 식으로만 진행하면 된다!

 

  다만 이 경우 O(N*N^3) = O(N^4) 이라서 시간초과를 피하기 힘들 것이다. 약간만 생각해보면, 예를들어서 현재 6명이 리스트에 남아있고 4001단계이다. 그럼 4001 실제로 6명을 가지고 약640억번 돌아볼게 아니고, 어차피 한바퀴 돌면 제자리일테니 640억을 6으로 나눈만큼만 돌면 된다! 4001^3 % 6 = 5이다. 이런식으로 A단계에 대해 'A^3 % [현재남은수]'를 계산해서 그만큼만 움직이면 된다. 그럼 총 O(N^2)으로 줄어든다.

 

  추가로 int가 연산이 더 빠르므로 세제곱근을 int 범위 내에서 한번 구해보자. 이건 이하의 나머지 연산의 분배법칙을 사용하면 된다. 

즉, a^3%m = (a*a*a)%m = (a%m * a%m * a%m) %m 이다.

그리고 a의 최대치는 4999이므로 m이 몇이더라도 4999*4999는 int 범위 이내이므로 문제없이 사용 가능하다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;

public class Main {
    private int getPow3WithMod(int i, int mod) {
        int ans = i;
        ans*=i;
        ans%=mod;
        ans*=i;
        return ans%mod;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> arr = new LinkedList<>();
        for (int i = 1; i <= n; i++) arr.add(i);
        int bf = 0;
        for (int i = 1; i < n; i++) {
            int removeNum = (bf + getPow3WithMod(i, arr.size()) - 1) % arr.size();
            if (removeNum < 0) removeNum+=arr.size();
            arr.remove(bf=removeNum);
        }
        System.out.println(arr.get(0));
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}