https://www.acmicpc.net/problem/21315
21315번: 카드 섞기
마술사 영재는 카드 더미를 이용한 마술을 개발하였다. 카드들에는 1부터 N까지의 숫자가 적혀있으며 초기 상태에는 1이 맨 위에 있으며 N개의 카드가 번호 순서대로 쌓여있다. 영재는 마술을
www.acmicpc.net
풀이 방법
모든 가능한 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;
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 11052 카드 구매하기 자바(java) (0) | 2024.01.31 |
|---|---|
| 백준 17609 회문 자바(java) (2) | 2024.01.31 |
| 백준 16166 서울의 지하철 자바(java) (0) | 2024.01.30 |
| 백준 19638 센티와 마법의 뿅망치 자바(java) (1) | 2024.01.29 |
| 백준 17281 야구⚾ 자바(java) (0) | 2024.01.29 |