분할정복. [2104]

[1. 문제 설명]

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

---

[2. 풀이 접근]

문제만 읽어 보면 구간 트리로 해결 할 것 처럼 보인다.

• 구간의 합을 O(N) 에 구하지 않아야 한다.
• 구간의 최소 값을 O(N) 에 구하지 않아야 한다.

그러나 구간 트리는 구간 내 값이 변화 할 때 사용 하는 의미가 있다.

구간 내 값이 변하지 않는 다면, 부분 합을 통해 구간 합을 O(1) 에 구할 수 있기 때문이다.

 

분할 정복 구현 패턴을 따른다.

1. 기저 사례, 한번에 해결 할 수 있는 경우
2. 왼쪽 구간에 대한 재귀 호출
3. 오른쪽 구간에 대한 재귀 호출
4. 전체 구간에 대한 O(N) 내 문제 해결

전체 구간에 대한 O(N) 내 문제 해결

1. 먼저 mid 와 (mid+1) 에 대한 문제를 해결한다.
   # (이 두 구간은 분할 과정에서 확인 해보지 않은 조합이다.
2. 이제 mid 는 left 까지 // (mid+1) 은 right 까지 이동한다.
   => 왼쪽 혹은 오른쪽 중 어느쪽으로 이동 할 지 선택.
   => 둘 중 당연히 큰 값이 구간에 포함되는 것이 이득일 것이다.
   => 단, 현재 까지 확장 한 구간에서 최소 값이 더 낮아진다면 연산 결과는 더 작아질 수 있으나,
   => 값을 업데이트 하지 않으면 상관 없다.

---

[3. 코드]