[백준 1806번] 부분합

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

1806번: 부분합

문제 풀이 (JAVA)

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

public class baekjoon1806 {
	static int[] arr;
	static int N;
	static int S;

	public static void main(String[] args) throws IOException {
		// 부분합
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken()); // 수열 개수
		S = Integer.parseInt(st.nextToken()); // 구하고자 하는 부분합

		arr = new int[N];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int result = subTotal(); // 부분합 구하는 함수 호출

		System.out.println(result);
	}

	private static int subTotal() {
		int lt = 0, rt = 0; // 왼쪽 포인터 , 오른쪽 포인터 변수
		int sum = 0;
		int min = Integer.MAX_VALUE;
		int pnum = 0; // 포인터간 거리 변수

		while (rt < arr.length) {
			if (sum >= S) {
				pnum = rt - lt; // 포인터간 거리 = 부분합의 개수

				min = Math.min(min, pnum); // 최소 부분합 개수 비교

				sum -= arr[lt++]; // 왼쪽 포인터 증가
			} else if (sum < S) {
				sum += arr[rt++]; // 오른쪽 포인터 증가
			}
		}

		if (min == Integer.MAX_VALUE) { // 최솟값의 변화가 없다면 0을 반환
			return 0;
		}

		return min;
	}

}

 

주요 핵심 포인트

1. 투 포인터의 개념을 응용한 문제로 투 포인터  개념 공부가 필요하다.

2. while문에서 오른쪽 포인터의 값이 끝인지만 체크하는 이유는 sum이 구하고자 하는 부분합 S 보다 클 경우, 왼쪽 포인터를 1씩 증가시키고, 부분합 S보다 작을 경우에는 오른쪽 포인터를 증가시키기 때문에 동적으로 부분합의 개수를 구할 수 있게 된다.

3. min == MAX_VALUE라면 수열의 모든 부분합이 S를 넘기지 못하였을 때 0을 리턴해주고 함수가 종료 된다.  

 

개선해야할 사항

: 처음에는 lt의 값을 체크하는 while문을 넣어 총 2개의 while문을 사용하였다. 하지만 rt의 값만 체크하는 while문 만으로도 투포인터를 풀 수 있다는 것을 알게 되었다. 투 포인터에 대한 개념을 좀 더 자세히 가져 갈 수 있도록 해야겠다.