[Python] 백준 22965 k개의 부분 배열

문제 링크 : https://www.acmicpc.net/problem/22965

22965번: k개의 부분 배열

1. 접근 방법

간단한 정렬 구조를 묻는 문제라 생각했다.

만약 횟수 제한 또는 한 번에 하려면 몇 조각으로 나누어야 하냐는 문제라면 조금 더 까다로울 수도 있었지만, 제한 없이 반복할 수 있어서 3조각으로 나눌 수 있으면 무조건 가능하다. 3조각으로 나누면 한 개씩 잘라내서 원하는 자리에 넣는 작업만 반복해도 된다.

또한 정렬되어 있으면 1이 되는것은 주어진 예제에서도 알 수 있다.

문제는 언제 2번만 가능한지를 구현하는 것이다.

 

 

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/22000/22965.py

GitHub - mintropy/baekjoon_py

📕코드 해설

코드 주석에도 달아둔 세가지 반례만 잘 처리하면 이 문제는 어렵지 않게 해결할 수 있을 것이라 생각한다.

우선, 코드의 큰 흐름은, 2조각으로 나누기 위해 가능한지 확인하는 것으로 진행된다.

만약 증가 수열이면증가수열이면 1을 출력하면 되므로, 조각의 수를 1로 설정하고 탐색한다. 만약 증가수열이면 조각의 수는 변하지 않고 1을 출력할 수 있다.

 

2조각으로 가능하기 위해서는, 수열을 두 부분 수열로 나눌 수 있고, 각각 부분 수열이 증가수열이여 한다. 그리고 가장 중요할 수 있는 부분인데, 오른쪽 부분 수열의 어떤 수가 왼쪽 부분 수열 사이에 들어가야 정렬되는 경우가 있으면 3조각이 돼야 한다.

만약 1 5 9 2 3 4의 경우, 1 5 9와 2 3 4 모두 정렬되어 잇는 부분 수열이지만, 전체를 정렬하기 위해서는 2 3 4가 1과 5 사이에 들어가야 정렬되기 때문에 3조각이 돼야 한다.

 

따라서 증가수열 규칙이 깨지면 조각을 하나 더하고, 두 번째 조각인데 앞의 정렬된 부분 수열 사이에 들어가야 하면 조각의 수를 또 하나 더하는 것으로 이 문제를 해결할 수 있다.

 

 

3. 생각 정리

간단한 정렬 문제인데, 코너 케이스 때문에 조금 고생했다.

조금 더 다양한 테스트 케이스를 만들어보고, 다양한 경우의 수를 고려하는 게 중요할 것 같다.