[BJ]11866, 1158, 1168, 11025 요세푸스 문제 n

BJ 11866, 1158, 1168, 11025 요세푸스 문제 n

 

 

문제링크

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

 

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

https://www.acmicpc.net/problem/1168

1168번: 요세푸스 문제 2

https://www.acmicpc.net/problem/11025

11025번: 요세푸스 문제 3

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/SyP7_i8FQ4k

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2023/08/15
 * @see https://www.acmicpc.net/problem/11866
 * @git 
 * @youtube  
 * @performance 12988	116
 * @category #자료구조, #Queue
 * @note 
 */

public class BJ_S5_11866_요세푸스문제_0{
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static int N, K;
    private static Queue<Integer> queue;
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());

        queue = new ArrayDeque<>();
        for(int i=1; i<=N; i++){
            queue.offer(i);
        }
        output.append("<");
        for(; !queue.isEmpty();){
            // K-1번째 까지는 빼서 뒤로 이동
            for(int k=0; k<K-1; k++){
                queue.offer(queue.poll());
            }
            // K 번째는 제거
            output.append(queue.poll()).append(", ");
        }
        output.delete(output.length()-2, output.length()).append(">");
        System.out.println(output);
    }

    // REMOVE_START
    private static String instr = "7 3";
    // REMOVE_END
}



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2023/08/15
 * @see https://www.acmicpc.net/problem/1158
 * @git 
 * @youtube  
 * @performance 12296	108
 * @category #자료구조, #List
 * @note 
 */

public class BJ_S4_01168_요세푸스문제{
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static int N, K;
    private static List<Integer> list; // index로 접근하기 위해서.
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());
        list = new ArrayList<>();
        for(int n=1; n<=N; n++){
            list.add(n);
        }
        output.append("<");
        for(int n=0, target=0, size=N; n<N; n++, size--){
            target = (target + K-1) %size;
            output.append(list.remove(target)).append(", ");
        }
        output.delete(output.length()-2, output.length()).append(">");
        System.out.println(output);
    }

    // REMOVE_START
    private static String instr = "7 3";
    // REMOVE_END
}



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2023/08/15
 * @see https://www.acmicpc.net/problem/1168
 * @git 
 * @youtube  
 * @performance 20288	236
 * @category #자료구조, #세그먼트트리
 * @note 
 */

public class BJ_P3_01168_요세푸스문제_2{
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static int N, K;
    private static SegmentTree tree;
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());

        tree = new SegmentTree(N);
        output.append("<");
        for(int n=0, target = 0, size=N; n<N; n++, size--){
            target = (target + K-1) %size;
            int orgNum = tree.find(1, 1, N, target+1);
            output.append(orgNum).append(", ");
        }
        output.delete(output.length()-2, output.length()).append(">");
        System.out.println(output);
    }

    static class SegmentTree{
        int [] data;

        public SegmentTree(int size){
            // 2^h = size;
            int h = (int)Math.ceil( Math.log(size) / Math.log(2));
            data = new int[(int)Math.pow(2, h+1)];
            init(1, 1, N);
        }

        private int init(int node, int s, int e){
            // 시작의 번호와 끝의 번호가 같다면 = 1
            if(s==e){
                return data[node] = 1;
            }
            // 나머지는 절반씩 나눠서 왼쪽 노드, 오른쪽 노드로 구분 초기화 - 값을 합쳐서 반환
            else{
                int mid = (s +e)/2;
                return data[node] = init(node*2, s, mid) + init(node*2+1, mid+1, e);
            }
        }

        private int find(int node, int s, int e, int order){
            // 방문한 노드들은 1씩 감소
            data[node]--;
            if(s==e){
                return s;
            }else{
                int mid = (s+e)/2;
                // 왼쪽에 내가 죽일 대상이 있나?
                if(data[node*2]>=order){
                    return find(node*2, s, mid, order);
                }else{
                    return find(node*2+1, mid+1, e, order - data[node*2]);
                }
            }
        }
    }
    // REMOVE_START
    private static String instr = "7 3";
    // REMOVE_END
}



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2023/08/15
 * @see https://www.acmicpc.net/problem/1168
 * @git 
 * @youtube  
 * @performance 11784	128
 * @category #DP
 * @note 
 */

public class BJ_P5_11025_요세푸스문제_3{
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static int N, K;
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());

        int A = 1;
        for(int n=2; n<=N; n++){
            A = (A + K-1)%n+1;
        }
        System.out.println(A);

    }

    
    // REMOVE_START
    private static String instr = "7 3";
    // REMOVE_END
}