투포인터 증명하기
https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
투포인터에서 정답을 찾기 위해 봐야하는 모든 케이스는 아래와 같다.
하지만 사실 부분합을 찾기 위해 모든 케이스를 탐색하지 않아도 된다.
검은색 부분은 볼 필요 없다. 투포인터는 봐야할 위치에 의미를 부여해 볼 필요없는 위치를 제외하고, 봐야하는 위치만 볼 수 있게 한다. 왜 안봐도되는지는 아래에 설명한다.
빨간 색 구간은 찾아야하는 값 15를 초과할 것이 당연히 예상되는 부분이므로 탐색할 가치가 없다. 직전값들이 이미 15이상이기 때문이다.
초록 박스 구간은 예를들어 [1,4] = 15이하라면 [2,4] 는 반드시 15보다 작으므로 탐색할 필요가 없기 때문이다. 위의 케이스에서 [1,4] = 14 이고, [2,4] = 9로 반드시 15보다 작다. 따라서 탐색하지 않는다.
이렇게 필요하지 않은 부분을 탐색하지 않기때문에, 투 포인터는 모든 부분합을 탐색할 수 있는 것이다.
참고
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] 버블정렬과 삽입정렬 (0) | 2022.09.22 |
|---|---|
| [알고리즘] 코테 복기 기록 (0) | 2022.08.07 |
| 누구나 이해할 수 있는 백준 드래곤 커브 풀이 파이썬 (0) | 2022.07.22 |
| 백준 빗물 14719번 파이썬 풀이 (0) | 2022.07.11 |
| 백준 14499번 주사위 굴리기 파이썬 풀이 (0) | 2022.06.02 |