[백준 1806] 부분합 (자바)

백준 1806번 부분합 (자바)

 

 

 

출처

www.acmicpc.net/problem/1806

1806번: 부분합

 

 

 

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

 

 

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

 

 

 

입출력 예

 

 

 

걸린 시간

 

 

 

접근 방법

예시를 보면 15를 만들 수 있는 가장 짧은 것의 길이를 구해야 한다.

10, 5를 사용하면 길이가 2이기 때문에 2를 return하면 된다.

 

풀이는 구간합 변수를 만들어 합이 원하는 수(s)보다 작으면 더 큰 수를 더해야 하기 때문에 배열의 원소를 더 해주면서 end+1를 하면서 범위를 늘려가고 더 커지면 구간의 거리를 거리 변수에 담아주면서 탐색 시작 범위를 오른쪽으로 옮기면서 

범위에 해당하지 않게 되는 원소를 합에서 빼줍니다.

 

end가 배열의 범위(n)을 넘게 되면 연산을 종료시키고, 이후에 거리 값이 초기값과 같으면 합을 만드는 것이

불가능한 경우이므로 0을 출력하고, 가능하다면 거리를 반환한다.

 

 

 

내 코드

 

 

고려할 점

1. 투 포인터 사용!

2. 구간합 사용

3. 거리 구하기