[종만북] JOSEPHUS - 조세푸스 문제 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-JOSEPHUS

 

풀이

  문제에서 제시된 방식대로 시뮬레이션을 돌려도 통과되는 문제이다. 실제로 2개가 남을 때 까지 List에서 제거하는 방식으로 시뮬레이션을 돌려서 풀었다. 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    private static final int LIMIT = 8030 * 1000;

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine());
        while (c-->0) new Main().solution();
        System.out.print(sb);
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        for (int i = 2; i <= n; i++) {
            List<Integer> candidates = new ArrayList<>();
            for (int j = 1; j <= n; j++) {
                candidates.add(j);
            }

            int die = 0;
            while (candidates.size() > 2) {
                if (candidates.remove(die) == i) break;
                die += k-1;
                die %= candidates.size();
            }

            if (candidates.size() != 2) continue;

            sb.append(candidates.get(0)).append(' ').append(candidates.get(1)).append('\n');
            break;
        }
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.