[Python] 백준/BOJ 31395번: 정렬된 연속한 부분수열의 개수 (Silver 4)

💻 Problem

문제 보러 가기

 

길이가 N인 수열 A_1, ..., A_N이 주어집니다. 수열의 모든 수는 서로 다른 1 이상 N 이하의 수입니다. 아래 조건을 모두 만족시키는 (i, j) 정수쌍의 개수를 구하세요.

•  1 <= i <= j <= N.
•  A의 i번째 수부터 j번째 수까지가 오름차순으로 배열되어 있다. 즉, i <= k < j를 만족하는 모든 정수 k에 대해 A_k < A_{k+1}.

 

💡 Approach

처음에 예제 이해가 잘 안됐는데 문제 내용은 아래와 같다.

(i, j) 구간의 수열이 정렬된 연속한 부분수열이면 만족한다.

만족하는 경우의 (i, j) 정수쌍 개수를 구하면 된다.

 

N의 범위가 1 <= N <= 200,000이므로 이중반복문을 쓰면 안 된다.

반복문을 하나만 쓰는 방법을 생각해야 한다.

 

오름차순 구간 길이에 따른 (i, j) 쌍 개수를 구해보면 아래와 같다.

오름차순 구간 길이	(i, j) 쌍 개수	가능한 (i, j) 쌍
1	1	(1, 1)
2	3	(1, 1), (1, 2), (2, 2)
3	6	(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)
4	10	(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)

...

이를 식으로 도출하면 오름차순 구간 길이가 s일 때, (i, j) 쌍 개수는 s * (s + 1) // 2가 된다.

 

✏️ Solution

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

cnt = 0
s = 1

for i in range(1, N):
    if A[i - 1] < A[i]:
        s += 1
    else:
        cnt += s * (s + 1) // 2
        s = 1

cnt += s * (s + 1) // 2

print(cnt)

• 시간복잡도: O(n)