[백준 2104] 부분배열 고르기 [C++]

백준 2104 - 문제

백준 2104 - 입/출력

---

풀이

일반적으로 범위가 넓을수록 최솟값과의 곱으로 인해 점수가 작을것이다.

때문에, 최솟값을 기준으로 나눈 영역(최솟값을 제외한 나머지 영역)에 대해 점수를 구할 때 높은 점수를 기대할 수 있다.

 

그러기 위해서는 먼저, 구간별로 가지는 합과, 최솟값을 구해야 한다.

leaf를 입력받은 후 초기화를 진행해주자.

pair에 합과, 최솟값을 가지는 요소의 index를 넣어줬다.

위에서 언급했듯, 최솟값을 기준으로 나눈 영역의 범위를 설정하기 위해서 value가 아닌 index를 넣어줬다.

 

구간별로 점수를 계산하기 위해 query를 작성해주었다.

주어진 구간에 대한 합과 최솟값의 index로 이루어진 pair를 반환한다.

초기화 단계에서는 올바르지 않은 요소를 접근하지 않는다.

하지만 위의 query는 올바르지 않은 범위에 대해 {0, 0}을 반환한다.

구간의 합 연산에는 문제가 없지만, 최솟값을 반환하는게 아닌, 최솟값이 들어있는 index를 반환하는 방식이기에,

leaf[0]을 최댓값으로 설정해 연산실수를 방지하자.

이제 최솟값의 index를 기준으로 divide and conquer을 통해 최대 점수를 구하면 된다.

우선, 구간이 자기 자신인 경우 구간합과 구간최솟값이 자신이므로 제곱값을 반환하자.

때문에 leaf를 long long 으로 선언하든가 연산과정에서 오버플로우가 일어나지 않게 explict casting을 해주자.

 

그 이후로는 아래의 구간에 대해 최대점수를 구해야 한다.

• 구간 i ~ j의 점수
• 구간 i ~ (min_idx - 1)의 점수
• 구간 (min_idx + 1) ~ j의 점수

---

소스코드

소스코드 보기

---

출처

2104번: 부분배열 고르기