높이가 작은 인접한 성냥으로 불을 옮길 때 가장 많은 성냥에 불을 태우는 방법

8685번: Zapałki (acmicpc.net)

 

n개의 성냥이 일렬로 있을때, 어떤 성냥에 불을 붙이면 인접한 성냥으로 불이 옮겨간다

 

이때, 불이 옮겨가는 조건은 해당 성냥보다 작거나 같은 높이를 가진 인접한 성냥으로 옮겨간다

 

최대한 많은 성냥을 태우기 위해 어떤 성냥에 불을 붙여야하는가?

 

예를 들어 [2,3,1,2]이면 1번 원소 3에 불을 붙이면 0번, 1번, 2번에 불이 붙으므로 3개 불을 붙일 수 있다

 

 

각 원소마다 불을 붙였다고 했을때 왼쪽 방향으로 불을 옮길 수 있는 개수, 오른쪽 방향으로 불을 옮길 수 있는 개수를 구할 수 있다

 

왼쪽 방향으로 불을 옮길 수 있는 개수를 left = [1,1,1,1]이라고 초기화하고 [2,3,1,2]에 대해서 생각해보면

 

1번 원소 3은 0번 원소보다 크므로 1번 원소에서는 0번 원소가 왼쪽 방향으로 불을 옮길 수 있는 개수만큼 더 옮길 수 있게 된다

 

즉, left[1] += left[0]

 

 

하지만 2번 원소 1은 1번 원소 3보다 작으므로 2번 원소는 1번 원소가 왼쪽 방향으로 불을 옮길 수 있는 개수만큼 옮길 수는 없다

 

3번 원소 2는 2번 원소 1보다 크므로 2번 원소가 왼쪽으로 옮길 수 있는 만큼 옮길 수 있으니까 left[3] += left[2]

 

그러면 left = [1,2,1,2]

 

1번 원소 3에 불을 붙이면 0번,1번에 불을 옮길 수 있으므로 2개가 맞다

 

 

비슷한 접근으로 right = [1,1,1,1]로 초기화하고 각 성냥에 불을 붙였을때 오른쪽 방향으로 옮길 수 있는 개수는?

 

2번 원소 1은 3번 원소 2보다 작으므로 3번 원소가 오른쪽 방향으로 옮길 수 있는 만큼 옮길 수는 없다

 

1번 원소 3은 2번 원소 1보다 크므로, 2번 원소가 오른쪽 방향으로 옮길 수 있는 만큼 옮길 수 있게 된다.

 

즉, right[1] += right[2]

 

0번 원소 2는 1번 원소 3보다 작으므로 1번 원소가 옮길 수 있는 만큼 옮기지는 못한다

 

그래서 right = [1,2,1,1]

 

 

left,right를 안다면 각 성냥이 왼쪽, 오른쪽으로 불을 옮길 수 있는 개수를 알 수 있다

 

left[i] + right[i] - 1

 

-1을 하는 이유는? 처음에 left, right를 1로 초기화 했기 때문에 자기 자신이 left[i] + right[i]에 2번 더해져서...

 

1을 빼줘야 1번만 더해지니까

 

따라서 left,right 배열을 찾고 left[i] + right[i] - 1중 최댓값을 찾으면 된다

 

#각 성냥에 불을 붙이고 높이가 작거나 같은 성냥으로 양쪽으로 불을 옮길 때,
#최대로 불을 옮길 수 있는 개수?

n = int(input())

A = list(map(int,input().split()))

left = [1]*n
right = [1]*n

#각 성냥이 왼쪽 방향으로 불을 옮길 수 있는 개수
for i in range(1,n):
    
    #i-1번 원소가 i번 원소보다 높이가 작거나 같다면
    #i번 원소는 i-1번 원소가 왼쪽으로 옮길 수 있는 개수만큼 더 옮길 수 있다
    if A[i] >= A[i-1]:
        
        left[i] += left[i-1]

#각 성냥이 오른쪽 방향으로 불을 옮길 수 있는 개수
for i in range(n-2,-1,-1):
    
    #i+1번 원소가 i번 원소보다 높이가 작거나 같다면
    #i번 원소는 i+1번 원소가 오른쪽으로 옮길 수 있는 개수만큼 더 옮길 수 있다
    if A[i] >= A[i+1]:
        
        right[i] += right[i+1]

answer = 0

for i in range(n):
    
    #각 성냥이 옮길 수 있는 개수는 left[i] + right[i] - 1
    #left,right 초기화가 1이므로 left[i] + right[i]에 자기 자신이 2번 더해짐
    v = left[i]+right[i]-1

    if answer < v:
        
        answer = v

print(answer)