백준 17074번: 정렬

백준 17074번: : 정렬

 

배열에 저장된 수를 하나씩 제외해서 배열 전체가 정렬이 되는지 확인하면 시간제한을 초과합니다.

경우의 수를 나눠

i) 이미 정렬이 되어 있는 경우

- 이미 배열이 정렬 되어 있으므로 어느 수를 버리더라도 정렬이 유지되므로 N개의 경우의 수가 나옵니다.

ii) 한 구간 빼고 정렬이 되어 있는 경우

- array[i-1] <= array[i+1] (i번째 배열의 방이 정렬되지 않은 수) 인 경우 i번째 배열의 방을 제거하면 전제 배열이 정렬됩니다.

-array[i] <= array[i+2] (i번째 배열의 방이 정렬되지 않은 수) 인 경우 i+1번째 배열의 방을 제거하면 전체 배열이 정렬됩니다.

->위의 두 가지 조건을 모두 만족하면 경우의 수는 2, 한 가지만 만족하면 경우의 수는 1, 모두 만족하지 못하면 경우의 수는 0을 출력하면 됩니다.

iii) 두 구간 이상 정렬이 되어 있지 않은 경우

- 어느 수를 버리더라도 정렬이 되지 않으므로 0개의 경우의 수가 나옵니다.