[インフラストラクチャアルゴリズムの解答]プリンセスを救う

質問する
インフラストラクチャアルゴリズムの問題を解く

The copyright in this matter is in Inflearn

入力

8 3

しゅつりょく

7

に答える
これはジョセフスに関する問題で、nとkがタイミングを与えると、1番からn番までの王子が時計回りに回転して、彼を円に座らせた.
1番王子から時計回りに回り、1番から番号を呼ぶ.一人の王子がkと叫ぶと.
その王子は排除され、次の王子から番号を叫び始めた.このまま最後まで.
王子の番号を印刷します.
n=8とk=3です.
1 2 3 4 5 6 7 8
1 2 4 5 6 7 8
1 2 4 5 7 8
2 4 5 7 8
2 4 7 8
4 7 8
4 7
7
上記の手順で、王子は除外され、残りの7番の王子が答えになります.
コードでは、まず、
1.pは、1次元配列をすべて0に初期化します.
2.現在位置を表すposという変数を利用して、1番王子からナビゲートして番号を呼び出す
cntという変数を用いてp配列の0個の数を計算し、cntが3の場合、
配列を1に変更してチェックします.チェックするときにanscnt変数でカウントした人が何人いるかを数えます.
次にcntを0に再設定し、posを移動してカウントします.
2-1. それから最初の王子は番号を呼ぶ.
現在位置posがnより大きい場合はposを1に変更する必要があります.
2-2. カウントを続け、anscntがn-1の場合、繰り返し文から終了し、現在位置posを出力します.
(0番目のインデックスからpos-1)
コード#コード#

/*45. 공주구하기 (조세퍼스)*/
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.StringTokenizer;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        
        System.setIn(new FileInputStream("input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] p = new int[n];

        int pos = 0;
        int cnt = 0;
        int ansCnt = 0;
        while(true){
            pos++;
            if(pos > n){
                pos = 1;
            }
            if(p[pos-1]==0){
                cnt++;
                if(cnt == k){
                    p[pos-1] = 1;
                    cnt = 0;
                    ansCnt++;
                }
            }

            if(ansCnt == n-1){
                break;
            }
            
        }

        for(int i = 0;i<n;i++){
            if(p[i] == 0){                        
                System.out.println(i+1);
                break;
            }
        }
        
    }
}