25571번 - 지그재그 부분배열 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 102 | 32 | 23 | 38.333% |
문제
길이 n인 정수 배열 A가 있고 i번째 원소는 A[i]라 하자 (i = 1, 2, ..., n). 1 ≤ i ≤ j ≤ n 인 인덱스 i, j에 대해, A[i, j]는 i번째 원소부터 j번째 원소까지 총 (j-i+1)개의 원소로 구성된 A의 부분 배열이다 - 이 부분 배열의 길이는 (j-i+1)이다. 예를 들어 A = [2, 2, 1, 3, 2] 이라면 A[2, 3] = [2, 1]이고 A[3, 5] = [1, 3, 2]가 된다.
길이가 2 이상인 (즉, i < j) 어떤 부분배열 A[i, j]의 원소들이 증가/감소를 번갈아 반복하면 지그재그 부분배열이라 부르는데, 구체적으로 아래 조건 중 하나를 만족해야한다:
- 조건 1: i ≤ k < j 인 모든 k에 대하여 (k - i)가 짝수 일 때 A[k] < A[k+1] 이고 홀수일 때 A[k] > A[k+1] 을 만족함
- 조건 2: i ≤ k < j 인 모든 k에 대하여 (k - i)가 짝수 일 때 A[k] > A[k+1] 이고 홀수일 때 A[k] < A[k+1] 을 만족함
예를 들어 A = [2, 2, 1, 3, 2] 이라면 A[2, 3]과 A[3, 5]는 지그재그 부분배열이며, A[1, 2]나 A[1, 3]은 지그재그 부분배열이 아니다.
Alice는 A의 부분배열 중 지그재그 부분배열의 개수가 몇 개인지 알고 싶어한다. Alice를 도와주자.
입력
입력 첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 나누어 주어진다. 첫 줄에 n이 주어지고 둘째 줄에 n개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답인 지그재그 부분배열의 개수를 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 100,000
- -109 ≤ A[i] ≤ 109 (1 ≤ i ≤ n)
예제 입력 1
4 5 2 2 1 3 2 4 2 0 2 2 5 1 2 3 2 1 7 1 2 1 2 1 2 1
예제 출력 1
6 3 5 21
예제 1: A[2, 3], A[2, 4], A[2, 5], A[3, 4], A[3, 5], A[4, 5]가 지그재그 부분배열이다.
예제 2: A[1, 2], A[1, 3], A[2, 3]이 지그재그 부분배열이다.
예제 3: 추가 설명 없음.
예제 4: 길이 2이상인 모든 부분배열이 지그재그 부분배열이다.
시간 제한
- Java 8: 2 초
- Python 3: 1 초
- PyPy3: 1 초
- Java 8 (OpenJDK): 2 초
- Java 11: 2 초
- Kotlin (JVM): 2 초
- Java 15: 2 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호