22965(k개의 부분 배열) - 참고 - 해결

k개의 부분 배열

 

문제

 $N$개의 서로 다른 정수를 가진 배열 $A$가 주어진다.

당신은 어제 공격력이 양의 정수 $k$인 칼을 받았다. 이 칼이 있으면 배열에 아래와 같은 연산을 적용할 수 있다.

1. 배열을 $k$개의 조각으로 자른다.
2.  $k$개의 조각을 원하는 순서대로 재배열한다.
3. 재배열한 순서대로 조각들을 다시 합친다.

당신은 배열 $A$에 이 연산을 원하는 횟수만큼 적용하여 (한 번도 적용하지 않아도 괜찮다) 오름차순으로 정렬하려고 한다.

 $k$의 값에 따라 이 연산을 적절히 적용하면 $A$를 정렬하는 것이 가능할 수도 있고, 연산을 어떻게 잘 적용해도 정렬할 수 있는 방법이 없을 수도 있다.

이 때, 배열 $A$를 정렬할 수 있는 가장 작은 양의 정수 $k$의 값을 구하는 프로그램을 작성하자.

 

입력

첫째 줄에 배열의 길이 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots , A_n$이 공백으로 구분되어 주어진다.

 

출력

주어진 수열을 오름차순으로 만들 수 있는 가장 작은 양의 정수 $k$의 값을 출력한다.

 

제한

•  $1 \leq N \leq 200\,000$ 
•  $1 \leq A_i \leq 200\,000$ 
•  $i \neq j$이면 $A_i \neq A_j$, 즉 배열 $A$의 값들은 모두 서로 다르다.

---

처음 생각 한것이 몇 조각으로 몇 번해야 가능할까? 를 생각하다가 생각한것이 

3조각으로 나누면 무조건 가능하다는 것을 알아내었다.

방법은 가장 작은 숫자를 단독으로 자른 다음 맨뒤로 보내고 그 다음 작은 수를 차례로 계속 뒤로 보내면 가능하다.

그렇다면 1조각은 이미 정렬이 되어있는 상태고 2조각으로 될 수 있는 방법을 생각해보면 되었다.

처음 생각한것은 숫자가 올라가다가 작아지면 조각이 나뉘는거고 이게 2조각이면 가능하다고 생각하여 하였지만 

3

1 3 2

와 같은 경우 범위가 다른 조각이 다른 조각의 숫자 사이면 안된다는 것을 알아서 그러면 해당 조각이 사이에 들어가는 경우를 빼었지만 또 틀렸다.

5

3 5 6 1 4

와 같은 경우도 안된다.

내가 생각한 것은 뒤에 조각이 1조각일때만 적용되는 것이였다. 

그래서 생각한 것이 2조각일때 맨 마지막 조각이 맨 앞 조각보다 작으면 된다고 생각하여 풀었다.

import sys
input = sys.stdin.readline

N = int(input())

nums = list(map(int,input().split()))

# 무조건 한토막은 있기 때문
cnt = 1

for i in range(1,N):
    # 숫자가 줄어 들면 범위가 나뉘기 때문에
    # 1증가
    if nums[i-1] > nums[i]:
        cnt += 1
    # 3조각이면 무조건 3으로 가능하기 때문에 break
    if cnt == 3:
        break

if cnt == 1:
    print(1)
# 2 조각이지만 만약 섞여있는 경우면 2개로 불가능 
elif cnt == 2 and nums[0] > nums[N-1]:
    print(2)
else:
    print(3)