[백준/2104] 부분배열 고르기 (Python)

Problem : https://www.acmicpc.net/problem/2104

2104번: 부분배열 고르기

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:42:21

 

---

 

문제 설명

 

 

크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱한 것이 점수가 된다.

배열이 주어졌을 때, 최대의 점수를 갖는 부분배열을 골라내는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 정수 N이 주어진다. 다음 줄에는 A[1], …, A[N]을 나타내는 정수들이 주어진다. 각각의 정수들은 음이 아닌 값을 가지며, 1,000,000을 넘지 않는다.

 

출력

 

첫째 줄에 최대 점수를 출력한다.

 

입력 예시

 

6
3 1 6 4 5 2

 

출력 예시

 

60

 

 

---

 

풀이

 

잘 생각해 보면, 이 문제와 거의 동일하다.

 

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

 

차이가 있다면, 위 문제는 직사각형의 면적을 구하는(즉 최솟값 이상을 갖는 면의 너비) 문제이지만, 본 문제는 부분합을 이용하는 문제이다. 스택을 활용하거나, 세그먼트 트리를 사용하거나, 분할정복을 사용해보아도 된다.

 

2023.06.01 - [알고리즘 문제/백준] - [백준/1725] 히스토그램 (Python)

[백준/1725] 히스토그램 (Python)

 

동일한 문제를 풀이한 바 있다(이 경우는 분할 정복을 사용했다).

 

스택 문제로 풀이하면 O(N)의 시간복잡도 내에 빠르게 처리할 수 있다. min값을 기준으로 오름차순으로 스택을 쌓는다고 생각하자. 스택에 저장된 정보는 (입력값, 좌측 최대 유효 인덱스)이며, 여기서 최대 유효 인덱스란 현재 입력값이 최솟값임이 보장되는 가장 좌측 인덱스를 의미한다.

i번째 입력값에 대한 처리는 다음과 같다

 

• 스택 pop : 현재 우측에 더 작거나 같은 값이 들어왔으므로, 최솟값이 보장되는 가장 우측 인덱스는 i가 된다. 즉 pop한 입력값에 대해 좌측, 우측 최솟값 인덱스를 모두 알 수 있으므로, 이 입력값을 최솟값으로 하는 최대 결과값을 구할 수 있다. answer 업데이트한다. 또한, 현재 입력값은 지금 pop한 값보다 작음이 보장되므로 이 현재 입력값의 좌측 최대 유효 인덱스는 pop한 인덱스로 업데이트할 수 있다.
• 스택 push : 더 이상 스택에 pop할 조건이 없다면 스택에 (현재 입력값, 좌측 최대 유효 인덱스)를 삽입한다.

 

p.s. 약 6개월 간격으로 계속 맞닥뜨리는 문제인데도 풀 때마다 어려움을 겪는다. 제대로 배우지 못하고 까먹는 탓인 것 같은데... 다음에는 복습 겸 세그먼트 트리로도 풀이해보는 게 좋겠다. 이를 주제로 그림을 그려가면서 포스팅하는 것도 도움이 되겠다.

 

 

풀이 코드

N = int(input())
num_list = list(map(int, input().split()))
sum_list = [0]
for i in range(N) :
  sum_list.append(sum_list[-1] + num_list[i])

stk, ans = list(), 0

for i in range(N) :
  j = i
  while stk and stk[-1][0] >= num_list[i] :
    h, j = stk.pop()
    ans = max(ans, (sum_list[i] - sum_list[j])*h)
  stk.append((num_list[i], j))

while stk :
  h, j = stk.pop()
  ans = max(ans, (sum_list[-1] - sum_list[j])*h)

print(ans)

풀이 완료!