[1. 문제 설명]
...
[2. 풀이 접근]
1차 풀이 (실패)
- 구간의 합을 구하여 같은지 확인 한다.
=> [1, 5] 구간에 1~5 DVD 가 존재 할 경우 [1, 5] 구간의 부분 합은 1+2+3+4+5=15 가 되어야 한다. - 반례)
=> [2, 4] 구간이 1,3,5 로 이루어진 경우 2+3+4 == 1+3+5 == 9
=> 둘다 같은 값이나, 2, 3, 4 가 있어야 하나 1, 3, 5 가 있으므로 대여 조건을 만족하지 않는다.
올바른 풀이
- 구간의 최대, 최소를 모두 갖고 있는 경우 성공.
- [2, 4] 구간은 2,3,4 가 존재해야 한다.
- [2, 4] 구간의 최소, 최대는 2, 4 인 것이 자명하다.
- 시리즈는 1씩 증가하므로, [2, 4] 구간이 2 와 4 만 존재 할 수 는 없다.
[3. 코드]
[3.1. 실패한 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
| 구간 트리. [12899] (0) | 2022.11.02 |
|---|---|
| 구간 트리. [16975] (0) | 2022.11.01 |
| 구간 트리. [1517] (0) | 2022.10.30 |
| 구간 트리. [2357] (0) | 2022.10.29 |
| 구간 트리. [11505] (0) | 2022.10.29 |
