백준 2759 자바 - 팬케이크 뒤집기 (BOJ 2759 JAVA)

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

 

  알고리즘 분류를 굳이 따지자면 constructive, ad-hoc, greedy 쪽일 것 같음. 애초에 답으로 가능한 경우 어떤 것이든 출력하면 되기도 하고, 이런 류의 문제를 풀기위한 well-known 스러운 풀이도 없다고 판단되므로 논리적 추론을 통해 이 문제만의 풀이과정을 만들어야 하는 종류의 문제이다.

 

  Brute force로 모든 경우를 보면 최대 O(30^30) 이라는 괴랄한 수가 나오므로 절대 무리..

전 일단 가장 큰 수 부터 차례대로 맨 아래로 가야한다는 부분에 포인트를 맞추고, 그럼 위에서 k개를 뒤집는 방식으로 어떻게 가장 큰 수부터 차례대로 맨 아래로 내릴지 생각해봤다.

 

  결론적으로 제 풀이는 다음과 같음.

가장 큰 수 부터 차례대로 아래의 과정을 거침.

1. 현재 맨 아래로 내리려는 수의 위치를 찾음.

2. 원래 넣어야 할 위치(첫번째로 큰 수라면 가장 아래, 2번째로 큰 수라면 아래서 2번째, ..)라면 냅둠. (코드상 while(idx!=n))

3. 그 위치가 맨 위라면, 해당 수가 들어가야 하는 위치까지 전부 뒤집음. (코드상으로 40~41line)

4. 그렇지 않다면 찾은 인덱스까지 뒤집음 (코드상 42~43line) -> 그럼 맨 위로 올라오게 되므로 다시 '1'을 수행할 시 원하는 위치에 들어감.

 

이걸 반복하면 될꺼라 생각하고, 위의 ad-hoc 풀이 과정대로 구현함.

 

예를들어 문제의 예제 입력 1의 2번째 TC의 경우, 다음의 과정을 거침

 

시작 : [4 3 2 5 1]

1. 가장 큰 수인 5의 위치 찾음 -> 4번째 이므로 5를 맨 위로 올리기 위해 4번째까지 뒤집음 -> [5 2 3 4 1]

2. 다시 가장 큰 수인 5의 위치를 찾음 -> 1번째 이므로, 전체를 뒤집음 -> [1 4 3 2 5]

3. 이제 5는 완료되었으므로 냅두고 4를 찾음 -> 2번째 이므로 2번째까지 뒤집음 -> [4 1 3 2 5]

4. 이제 4를 내리기 위해 4번째까지 뒤집음 (5는 이미 답을 찾았으므로 냅둠) -> [2 3 1 4 5]

5. 다음 수인 3을 찾음. 2번째이므로 2번째까지 뒤집음 -> [3 2 1 4 5]

6. 마찬가지로 3번째까지 뒤집음 -> [1 2 3 4 5]

7. 다음 수인 2를 찾음 -> 원래 들어가야할 2번째에 있으므로 냅둠

8. 다음 수인 1을 찾음 -> 마찬가지로 이미 1번째이므로 냅둠

9. 끝

 

-> 최종적으로 뒤집기 과정은 총 6개로, 4 5 2 4 2 3와 같음. (문제에서 제시된 답과 다르지만 어쨌든 답이 되는 출력이라면 통과이므로 상관없음. )

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02700/BOJ_2759.java