(Elice / 정렬 / Python) 당신의 분할은?

당신의 분할은?

체셔를 통해 정렬 알고리즘의 중요성을 깨달은 엘리스는 체셔에게 자신있게 말했습니다.

“체셔! 나 이제 정렬 알고리즘에 대해서 마스터 한것 같아. 정말 뿌듯해!”

체셔가 답했습니다.

“그래?? 정말 뿌듯하네! 그럼 이제 분할 정복 알고리즘 문제를 해결하는데 문제없겠네??”

엘리스는 무엇인지 모를 오한을 느꼈지만 개의치 않았습니다.

“응!!! 당연하지! 내가 누군데!”

체셔는 저번과 같은 환한 미소를 지으며 말했습니다.

“좋아! 그럼 엘리스가 숫자로 이루어진 배열을 분할 정복 알고리즘으로 정렬을 하려고 할 때 최대 몇 가지 배열로 분할할 수 있을까??”

오늘도 무사히 넘어갈 리 없는 체셔에게 엘리스는 또 속았습니다!! 여러분이 엘리스를 도와 대신 대답해주세요.

 

일련의 숫자로 이루어진 배열이 주어집니다.

주어진 배열(Array)를 여러 부분 배열로 나누고, 각 부분 배열을 정렬한 후 이어붙일 때 전체 배열이 정렬된 상태가 되는 경우 중, 나눌 수 있는 부분 배열의 최대 개수를 출력하세요

입력 예시 1

3 2 1 0

출력 예시 1

1

• [3, 2, 1, 0]을 [3, 2] 와 [1, 0]으로 분할한다면 [2 ,3], [0,1] 이 되므로 분할 할 수 없습니다. 왜냐하면 분할된 배열을 합쳤을 경우 [2, 3, 0, 1]이 되어 제대로 정렬되지 않기 때문입니다. 따라서 이 경우 나눌 수 있는 최대 분할은 1 개, 즉 [3, 2, 1, 0] 뿐입니다.

입력 예시 2

2 3 0 1 4 5

출력 예시 2

3

• [2, 3, 0, 1]과 [4], [5]로 분할한다면 [0,1,2,3]과 [4],[5]로 정렬 할 수 있습니다.

 

입력

• 0 이상의 정수들로 이루어진 배열 A가 입력됩니다.
• 배열 A의 길이를 N이라고 하겠습니다.
• 배열 A에 들어 있는 정수들은, 0 이상 N 미만의 자연수이며 서로 중복되지 않습니다.

출력

• 주어진 배열(Array)를 여러 부분 배열로 나누고, 각 부분 배열을 정렬한 후 이어붙일 때 전체 배열이 정렬된 상태가 되는 경우 중, 나눌 수 있는 부분 배열의 최대 개수를 출력하세요.

소스 코드

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

cnt = 0

sum_index = 0
sum_value = 0

for i in range(len(arr)):
    sum_index+=i
    sum_value+=arr[i]
    if sum_index == sum_value:
        cnt+=1
        
print(cnt)