[BOJ 2759] 팬케익 뒤집기

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

💡 접근방법

팬케익을 순차적으로 뒤집기 위해서는 가장 큰 팬케익이 아래로 오도록 이동시키면 된다. 가장 큰 팬케익을 찾은 다음에 제일 위로 올리고, 맨 마지막으로 가도록 뒤집어주면 된다.

매순간 가장 큰 팬케익이 아래에 온다면, 맨아래에 위치된 가장 큰 팬케익을 제외하고 나머지 팬케익들에 대해서도 동일하게 확인하면 된다.

이 문제에서는 가장 짧은 플립 시퀸스를 찾을 수 있을까? 불가능하다. 이 문제는 NP-Hard라는 것이 증명되어 있다.

💡 해설코드

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	static int getMax(int[] arr, int start, int end){
		int ret = -1;
		int idx = -1;
		
		for(int i = start; i <= end; i++){
			if(ret < arr[i]){
				ret = arr[i];
				idx = i;
			}
		}
		
		return idx;
	}
	
	static void rotate(int[] arr, int start, int end){
		for(int i = start; i <= end / 2; i++){
			int tmp = arr[i];
			arr[i] = arr[end - i];
			arr[end - i] = tmp;
		}
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int T, N;
		int[] arr;
		String[] sArr;
		
		T = Integer.valueOf(br.readLine());
		
		for(int i = 1; i <= T; i++){
			List<Integer> list = new ArrayList<>();
			sArr = br.readLine().split(" ");
			
			N = Integer.valueOf(sArr[0]);
			arr = new int[N];
			
			for(int j = 0; j < N; j++){
				arr[j] = Integer.valueOf(sArr[j + 1]);
			}


			int start = 0;
			int end = arr.length - 1;
			
			while(start != end){
				int maxIdx = getMax(arr, start, end);
				
				if(maxIdx == start){
					rotate(arr, start, end);
					list.add(end + 1);
				}else if(maxIdx != end && maxIdx != start){
					rotate(arr, start, maxIdx);
					rotate(arr, start, end);
					
					list.add(maxIdx + 1);
					list.add(end + 1);
				}
				
				end--;
			}
			
			System.out.print(list.size() + " ");
			for(int j = 0; j < list.size(); j++){
				System.out.print(list.get(j) + " ");
			}
			System.out.println();
		}
	}
}