사용자 도구

사이트 도구


ps:problems:boj:31395

정렬된 연속한 부분수열의 개수

ps
링크acmicpc.net/…
출처BOJ
문제 번호31395
문제명정렬된 연속한 부분수열의 개수
레벨실버 4
분류

조합론

시간복잡도O(n)
인풋사이즈n<=200,000
사용한 언어Python 3.11
제출기록55060KB / 116ms
최고기록104ms
해결날짜2024/02/05

풀이

  • 어떤 증가하는 연속한 수열의 연속한 부분수열들은 모두 증가하는 부분배열이다. 즉, A[x:x+l]이 증가 수열이라면, x≤i<j≤x+l 인 모든 i,j에 대해서 A[i:j]는 증가 수열이다. 이러한 i,j 쌍의 개수는 comb(l+1,2) 이다
  • 이제 원래 수열을 맥시멀한 연속된 증가수열들로 쪼개서, 각각의 수열마다 저 값들을 더해주면 된다.
  • 실제 구현은 l을 다 구한 뒤에 comb를 계산하는 대신에, l이 늘어날때마다 l값을 더해주는 식으로 구현했지만, 기본 원리는 똑같다.
  • 시간복잡도는 O(n)

코드

"""Solution code for "BOJ 31395. 정렬된 연속한 부분수열의 개수".

- Problem link: https://www.acmicpc.net/problem/31395
- Solution link: http://www.teferi.net/ps/problems/boj/31395
"""

import itertools


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    answer = 1
    inc_size = 1
    for prev, cur in itertools.pairwise(A):
        if prev < cur:
            inc_size += 1
        else:
            inc_size = 1
        answer += inc_size

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
B C T C W
 
ps/problems/boj/31395.txt · 마지막으로 수정됨: 2024/02/05 14:18 저자 teferi