백준 21315 카드 섞기 자바(java)

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

21315번: 카드 섞기

 

풀이 방법

모든 가능한 k 조합에 대해 완전탐색하면서 시뮬레이션하는 문제이다.

2^k 값이 N을 넘으면 안되므로 x = 2^k 이면 k = log2 (x) 임을 이용하여 최대 가능한 k 값을 구해주는 데, java 에서 Math.log 는 로그10 이므로 log2 (x) = log10 (x) / log10 (2) 공식을 사용하여 구해주었다.

 

첫번째 k 값을 k1, 두번째 k값을 k2 라고 할 때 두 값이 각각 1~최대 k 일 때를 이중 for문으로 돌려 모든 조합에 대해 시뮬레이션을 돌리도록 하였다. 시뮬레이션을 돌릴 땐 다음 상태를 저장할 배열 next 를 생성한 다음, next 배열의 0 인덱스부터 맨 위로 올릴 카드들을 앞에서부터 차례대로 저장해주고 그 뒤부터 나머지 카드들을 원래의 순서대로 저장해주도록 하였다.

주의할 것은 맨 위로 카드를 올릴 땐 직전에 맨 위로 올렸던 카드 중 마지막 위치한 카드가 맨 밑이 되므로 그 위치 정보를 저장해놓고 다음 단계에 올릴 때 사용해야 한다.

 

 

코드

import java.io.*;

public class Main {

    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        int[] goal = new int[N];
        int[] arr = new int[N];
        // 초기 카드 상태 저장
        for(int i=1; i<=N; i++) {
            arr[i-1] = i;
        }
        // 최종 상태 입력 받기
        for(int i=0; i<N; i++) {
            goal[i] = Integer.parseInt(line[i]);
        }

        int limit = (int)(Math.log(N) / Math.log(2));
        for(int k1=1; k1<=limit; k1++) {
            for(int k2=1; k2<=limit; k2++) {
                int[] tmp = new int[N];
                for(int j=0; j<N; j++) {
                    tmp[j] = arr[j];
                }
                // 2번의 (2, k)-섞기 진행
                simulation(k1, tmp);
                simulation(k2, tmp);
                if(check(tmp, goal)) { // 최종 상태와 같은지 체크
                    System.out.println(k1 + " " + k2);
                    return;
                }
            }
        }
    }

    public static void simulation(int k, int[] tmp) {
        // (2, k) - 섞기
        int pos = N;
        for(int i=1; i<=k+1; i++) {
            int[] next = new int[N]; // 다음 카드 상태 저장
            int up = (int)Math.pow(2, k-i+1); // 위로 올릴 카드 개수
            int idx = 0;
            // 2^k개의 카드 위로 올리기
            for(int j=pos-up; j<pos; j++) {
                next[idx] = tmp[j];
                idx++;
            }
            // 위에 올린 카드 제외하고 밑으로 순서대로 밀기
            for(int j=0; j<pos-up; j++) {
                next[idx] = tmp[j];
                idx++;
            }
            for(int j=pos; j<N; j++) {
                next[idx] = tmp[j];
                idx++;
            }
            // 상태 갱신
            for(int j=0; j<N; j++) {
                tmp[j] = next[j];
            }
            pos = up;
        }
    }

    public static boolean check(int[] tmp, int[] arr) {
        for(int i=0; i<N; i++) {
            if(tmp[i] != arr[i]){
                return false;
            }
        }
        return true;
    }
}