(JAVA) 백준 1806번 : 부분합 -- [투포인터]

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

1806번: 부분합

 

안녕하세요.

 

이 문제는 투포인터 문제 입니다.

 

10000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어지는데요.

이 수열에서 연속된 수들의 부분합 중 S 이상이 되는 수들 중 가장 짧은 것의 길이를 구해야합니다.

 

 

 

알고리즘

---

먼저,

1) start와 end를 0으로 초기화 한 후 while문에 진입하는데요.

초기 합은 index 0인 값으로 설정합니다.

 

while문 진입 시

2) 지금까지 더한 연속된 수들의 합과 S를 비교합니다.

2-1) 만약, S이상이라면 end - start + 1 과 현재 가장 짧은 길이를 비교해서 더 짧은 값을 저장합니다.

*** end - start가 합을 구할때 사용한 연속된수의 길이가 되니까요. 1을 더하는것은 end - start는 단순 index 숫자 계산이지 실제 개수는 아니기 때문에!

 

2-2) 다음, start 포인터를 한 칸 오른쪽으로 이동시킵니다(start++)

2-3) start 포인터를 옮겼기 때문에, 이전에 가리키던 숫자를 합에서 뺍니다. (연속된 수의 구간이 바뀌었기 때문)

2-4) continue로 다음 2의 과정부터 반복!

 

3) 2-1의 조건을 만족하지 않는다면, end를 한 칸 오른쪽으로 이동시킨 후 합에 해당 지점의 값을 더해줍니다.

 

4) 2의 과정부터 다시 반복!

 

 

간단하죠?

 

즉, start와 end 포인터(투포인터)를 만들어서 연속된 수의 합이 S 밑이면 당연히 값을 더 늘려야하니까 end를 오른쪽으로 옮기는 것이고,

연속된 수의 합이 S이상이면 당현이 S에 맞추기 위해 합을 줄여야하니 start를 오른쪽으로 옮기는 것입니다.

 

그렇게 windows(연속된 수의 길이) 를 변경시키면서 S이상인 조건을 찾고, 이때의 최소 길이를 구하면 됩니다.

 

 

이상입니다!

 

감사합니다.

 

 

 

소스코드

---