Informatica Online Judge

  일본 침몰 [2330 / 091A]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 21   Total Tried : 29


The Champion of this Problem (C++) : gs18094 - ms / 756byte
My Best Submission (C++) : N/A

[JOI2019예선]

Background

일본은 N개의 구역으로 이루어져 있다. 각 구역은 왼쪽으로부터 순서대로 1부터 N까지 번호가 부여되어 있다.

일본은 바다로 둘러쌓여 있으며, 해수면의 높이는 장소에 관계없이 일정하다. 높이가 수면보다 높은 구역을 육지라고 부른다.

연속된 육지로 구성된 구역을 섬이라고 부른다.

좀 더 엄밀피 표현하자면 정수 l, r (1 <= l <= r <= N) 에 대해서 구역 l, l+1, ... , r의 영역을 [l, r]이라고 한다. 다음 조건을 만족하는 구역 [l, r]을 섬이라고 부른다.

- 구역 ㅣ, ㅣ+1, ... , 구역 r이 모두 육지이다.
- l>1 일 때, 구역 l-1은 육지가 아니다.
- r이라면 구역 r+1은 육지가 아니다.

해수면의 상승에 따라 일본은 조금씩 침몰해 간다. 현재 해수면의 높이는 0이지만 시간의 경과에 따라서 해수면은 상승한다. 결국 일본은 완전히 침몰해버린다.

경곽이는 해수면의 높이의 상승에 따라 일본을 구성하는 섬의 수가 바뀐다는 사실을 알았다. 일본의 육지가 완전히 사라질 때까지 섬 개수의 최댓값을 구하는 프로그램을 작성하시오.

Input

입력은 다음의 형식으로 이루어진다.

N
A_1 A_2 ... A_N

1 ≦ N ≦ 100000 (= 10^5)
0 ≦ A_i ≦ 1000000000 (= 10^9) (1 ≦ i ≦ N)

[Sub-Task Info]
#1 : (7%) N ≦ 2000, A_i ≦ 2000 (1 ≦ i ≦ N)
#2 : (8%) N ≦ 2000
#3 : (85%) 추가 제한 조건은 없다.

Output

현재로부터 일본이 완전히 침몰할 때까지 섬의 개수의 최댓값을 구하여 출력한다.

IO Example

입력1
6
0 1 2 1 3 2

출력1
2

해수면의 높이가 0이상 1미만일 때 구역 2, 3, 4, 5, 6이 육지이고 이 영역은 유일한 섬이다. 따라서 섬의 개수는 1이다.

해수면이 1이상 2미만일 때 구역 3, 5, 6이 육지이고, 영역 [3, 3]과 영역[5, 6]이 섬이므로 섬의 개수는 2이다.

해수면의 높이가 2이상 3미만일 때는 섬의 개수는 1개, 해수면의 높이가 3이상이 되면 일본은 완전히 침몰하므로

최대 섬의 개수는 2개이다.

입력2
6
3 2 3 0 2 0

출력2
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]