15779번 - Zigzag 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 959 | 330 | 270 | 43.062% |
문제
어떤 수열에서, 연속된 3개의 수를 보았을 때, 그 수가 단조증가 수열이거나, 단조감소 수열인 경우가 없으면 이 수열을 "지그재그 수열" 이라고 말한다.
좀 더 정확하게는, 길이 N의 수열 A가 모든 1 이상 N-2 이하의 자연수 i에 대해서, Ai ≤ Ai+1 ≤ Ai+2도 만족하지 않고, Ai ≥ Ai+1 ≥ Ai+2도 만족하지 않으면, A는 지그재그 수열이다.
길이 N의 수열 A가 주어졌을 때, A의 연속된 부분 수열 중 지그재그 수열의 최대 길이를 구하여라.
길이 M의 B가 길이 N인 A의 연속된 부분 수열이라는 것은, 어떤 i가 존재 해서, B1 = Ai, B2 = Ai+1, ..., BM = Ai+M-1 인 것을 말한다.
입력
입력은 두 줄로 이루어져 있다. 첫째 줄에는 수열의 길이 N이 주어진다.
둘째 줄에는 공백으로 구분된 N개의 정수가 주어진다. i번째 수는 Ai를 의미한다.
출력
A의 연속된 부분 수열 중 지그재그 수열의 최대 길이를 구하여라.
제한
- 3 ≤ N ≤ 5,000
- 1 ≤ Ai ≤ 109 (1 ≤ i ≤ N)
서브태스크 1 (33점)
이 서브태스크는 다음의 조건을 만족한다.:
- N = 3
서브태스크 2 (37점)
이 서브태스크는 다음의 조건을 만족한다.:
- N ≤ 300
서브태스크 3 (30점)
이 서브태스크는 추가 제한 조건이 없다.
예제 입력 1
3 1 2 3
예제 출력 1
2
예제 입력 2
5 1 3 4 2 5
예제 출력 2
4
출처
University > KAIST > 2018 KAIST RUN Spring Contest Z번
- 문제를 만든 사람: koosaga
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호