[백준] G4 1806번 부분합 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1806번: 부분합

[문제] 

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

[입력]

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

[출력]

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

 

 

---

[풀이]

1. 처음부터 끝까지 탐색을 하면서 조건을 만족하는 지 체크를 해야 한다.

2. 왼쪽의 위치를 나타내는 left 포인터, 오른쪽의 위치를 나타내는 right 포인터를 만들어준다.

3. 요구합을 만족하는 경우 left 포인터를 증가시켜서 수열의 길이와 합을 감소시킨다.

4. 요구합을 만족하지 못하는 경우 right 포인터를 증가시켜 수열의 길이와 합을 증가시킨다.

5. 요구합을 만족하는 경우 오른쪽 포인터 - 왼쪽 포인터를 해줘 길이를 구하고 이 길이가 최소일 것을 구해준다.

5. 모든 배열을 탐색하였을 때, 가장 짧은 수열의 길이를 구해준다.

[접근]

1.  모든 탐색을 해야 하는데 반복문을 통해서 하면 시간이 너무 많이 걸리기 때문에 투 포인터를 사용해서 문제를 풀어야겠다고 생각했다.

2. 왼쪽(시작 점)과 오른쪽(끝 점)을 가리켜서 탐색을 하였다.

[코드]

package BOJ_gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_G4_1806 {
	static int n;
	static int s; // 요구합
	static int number[]; // 수열을 담을 배열
	static int sum; // 합
	static int result = 100001; // 최대로 들어왔을 때의 개수가 100000이니까 그거보다 큰 값으로 초기 설정
	static int left = 0; // 왼쪽 포인터
	static int right = 0; // 오른쪽 포인터

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		
		number = new int[n];
		
		// 수열 값 입력받기
		st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < n; i++) {
			number[i] = Integer.parseInt(st.nextToken()); // 수열 값 저장
		}
		
		while (true) {
			if (sum >= s) { // 합이 요구값이상이면
				sum -= number[left]; // 왼쪽에서 한칸 이동을 시키니까 합에서 감소
                result = Math.min(result, (right - left));
                // 현재의 길이와 지금까지의 최소 길이를 비교해서 최소값으로 갱신
                left++; // 왼쪽을 오른쪽으로 이동
			}
			else if (right == n) { // right가 n이다? 끝까지 탐색이 끝났다.
				break; // 탈출
			}
			else // 합이 요구값이상도 아니고, 끝도 아니라면
				sum += number[right++]; // 오른쪽을 증가
		}
		
		// 만약 결과가 처음 입력값과 같다면
		if (result == 100001) {
			System.out.println("0"); // 불가능한 것이니까 0출력
		}
		else // 아니면
			System.out.println(result); // 결과 출력
	}
}