알고리즘 및 자료구조/문제

algospot 조세푸스(JOSEPHUS)

ktko 2016. 3. 28. 00:38


문제링크



문제

1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고, 포위당한 N명의 사람들이 모두 원형으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방향으로 K번째 살아 있는 사람이 자살하는 것입니다.

조세푸스의 책에 따르면 조세푸스와 다른 병사 하나만이 살아남았을 때 이들은 마음을 바꿔 로마에 항복해서 살아남았다고 합니다. 마지막 두 명 중 하나가 되기 위해서는 조세푸스는 첫 번째 병사로부터 몇 자리 떨어진 곳에 있어야 했을까요?

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스는 두 개의 정수 N, K로 주어집니다(3≤N≤1000, 1≤K≤1000).

출력

각 테스트 케이스에 두 개의 정수로, 마지막 살아남는 두 사람의 번호를 오름차순으로 출력합니다. 첫 번째로 자살하는 병사의 번호가 1이며, 다른 사람들의 번호는 첫 번째 병사에서부터 시계 방향으로 정해집니다.


이 쉬운 문제를.. 왜 그동안 삽질했는지.. 잠깐 봤는데 .. 잠깐 끄적였더니 바로 풀렸다.
여기서 중요한건 처음 사람을 죽인 다고하니 0번째 부터 죽이는 것. 그리고 그 다음 사람을 죽이기 위해 killPoint라는 변수를 kill - 1이라고 했다. 
잘 생각해보면 1번째 살아있는 사람이 자살하게 된다면 그 다음 사람이 자살하게 됨으로 링크드 리스트에서 계속 0번째 맨 앞에 있는 사람이 죽게된다.
만약 3번째 살아있는 사람이 자살하게 된다면 killPoint 는 2가 될 것이다.

그리고 if (joList.size() <= point) point %= joList.size();) 조건이 중요하다. 현재 포인트가 리스트보다 크게 된다면 앞으로 넘어오게 되는데 조건을 충족시키기 위해 %를 이용하였다.



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

//JOSEPHUS
//https://algospot.com/judge/problem/read/JOSEPHUS
public class JOSEPHUS {
    static LinkedList<Integer> joList;
    static int testCase;
    static int[][] result;

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner scan = new Scanner(System.in); // 문자 입력을 인자로 Scanner 생성
        testCase = Integer.parseInt(scan.nextLine().trim()); // 키보드 문자 입력
        result = new int[testCase][2]; // 테스트 케이스 정답을 저장하는 배열

        for (int i = 0; i < testCase; i++) {
            int a = scan.nextInt(); // 사람 명
            int kill = Integer.parseInt(scan.nextLine().trim()); // 순서

            joList = new LinkedList<>();

            for (int j = 1; j <= a; j++) {
                joList.add(j);
            }

            int point = 0;
            int killPoint = kill - 1;

            for (int j = 0; j < a - 2; j++) {
                if (joList.size() <= point)
                    point %= joList.size();

                joList.remove(point);
                point += killPoint;
            }

            result[i][0] = joList.get(0).intValue();
            result[i][1] = joList.get(1).intValue();

        }

        for (int k = 0; k < testCase; k++)
            System.out.println(result[k][0] + " " + result[k][1]);
    }
}


저작자표시 (새창열림)
댓글수2