문제

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 이번에 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟다가 높이가 점점 낮은 돌을 밟으면서 개울을 지나가려고 한다. 돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

풀이

아이디어

• LIS인데, 계속 증가되는 돌을 밟다가 어느 순간 계속 감소되는 높이의 돌을 밟아 나가는 것이다.
• 그 "어느 순간"이 언제가 될 지 모르므로 다음과 같이 서쪽->동쪽의 경우와 동쪽->서쪽의 경우를 나눠서 생각하면 좋다.
  • 서쪽->동쪽으로 증가되는 돌만 밟아가는 경우
    • LIS 배열을 갱신해나가면서 현재까지 몇 개의 돌을 밟았는지도 다른 배열에 기록해주면서 나아간다.
  • 동쪽->서쪽으로 증가되는 돌만 밟아가는 경우
    • 이 경우는 서쪽->동쪽으로 감소되는 돌만 밟아가는 경우랑 동일하다.
    • 마찬가지로 LIS 배열을 갱신해나가면서 현재까지 몇 개의 돌을 밟았는지도 다른 배열에 기록해주면서 나아간다.
    • 이때 주의할 점은 동쪽->서쪽으로 밟아나가는 것이므로 현재까지 몇 개의 돌을 밟았는지는 배열의 왼쪽으로 갈수록 커진다. ex) [3, 2, 2, 2, 1]
• 이렇게 서쪽->동쪽으로 이동할 때, 동쪽->서쪽으로 이동할 때 각각 i라는 지점에서 몇 개의 돌을 밟아왔는지 알 수 있다. 그리고 이 i라는 지점이 우리가 말한 그 "어느 순간"이다.
• 따라서, i라는 순간에 서쪽->동쪽으로 이동하면서 밟은 돌 개수 + 동쪽->서쪽으로 이동하면서 밟은 개수가 최대가 되는 i 지점의 값을 구해주면 된다.
• 이때 주의해야 할 점은 그 합에서 1을 빼야 하는데, 왜냐면 그 지점의 돌은 두 번 밟은 셈이 되기 떄문이다.

코드

import sys
from bisect import bisect_left

N = int(sys.stdin.readline())
heights = list(map(int, sys.stdin.readline().split()))

#앞에서부터의 LIS
FRONT_LIS = [heights[0]]
FRONT_CNT = [1] * N
answer = 0
cnt = 1
for i in range(1, N):
  if heights[i] > FRONT_LIS[-1]:
    FRONT_LIS.append(heights[i])
    cnt += 1
  else:
    pos = bisect_left(FRONT_LIS, heights[i])
    FRONT_LIS[pos] = heights[i]
  
  FRONT_CNT[i] = cnt

#뒤에서부터의 LIS
heights.reverse()
BACK_LIS = [heights[0]]
BACK_CNT = [1] * N
cnt = 1
for i in range(1, N):
  if heights[i] > BACK_LIS[-1]:
    BACK_LIS.append(heights[i])
    cnt += 1
  else:
    pos = bisect_left(BACK_LIS, heights[i])
    BACK_LIS[pos] = heights[i]

  BACK_CNT[N-i-1] = cnt

for i in range(N):
  answer = max(answer, FRONT_CNT[i]+BACK_CNT[i])

print(answer - 1)