[SWEA 4411][D5][JAVA] 덕환이의 카드 뽑기

[문제]

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcL9nKpbEDFAV8

SW Expert Academy

 

[풀이방법]

 

처음에는 덱으로 해서 K만큼의 숫자를 뒤로 넘겨주고 맨 앞의 원소를 지워주는 과정을 반복해서 값을 구하려고 했는데 마지막 예시 

100000 10000000000

여기에서 시간이 너무 오래 걸려서 불가능했습니다. 

 

그래서 찾아보니 요세푸스 점화식을 사용해서 해결할 수 있었어요 

 

요세푸스 점화식 / 

N명의 사람 중 K번째의 사람이 자결하는데 마지막까지 살아남는 사람을 구하는 점화식입니다. 

 

https://statkclee.github.io/r-algorithm/r-josephus-problem.html

이 포스트를 보면서 이해했습니다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int T = Integer.parseInt(st.nextToken());
 
        StringBuffer sf = new StringBuffer();
        
        for (int k = 0; k < T; k++) {
            st = new StringTokenizer(br.readLine());
            long N = Long.parseLong(st.nextToken());
            long K = Long.parseLong(st.nextToken());
            
            long result = 0;
            
            for (int i =1; i <= N; i++ ) {
                result = (result + K) % i + 1;
            }
            sf.append("#" + (k+1) + " " + result + "\n") ;
            
        }
        System.out.println(sf.toString());
    }
}