[백준] 부분합 (1806번)

문제 흐름

1. 문제 목표
   • 주어진 정수 배열에서 연속된 부분 수열의 합이 주어진 수 S 이상이 되도록 하는 가장 짧은 부분 수열의 길이를 찾는 것입니다.
2. 입력 설명
   • 첫 번째 줄에 두 개의 정수 N (배열의 크기)과 SSS (목표 합) 이 주어집니다.
   • 두 번째 줄에는 N개의 정수가 배열의 요소로 주어집니다.
3. 출력 설명
   • 조건을 만족하는 가장 짧은 부분 수열의 길이를 출력하며, 그런 부분 수열이 없는 경우에는 0을 출력합니다.

 

핵심 아이디어

• 슬라이딩 윈도우 기법을 사용하여 두 포인터(시작점과 끝점)를 이동시킵니다.
• 현재 부분 수열의 합이 목표 합 S 이상이 될 때까지 끝점을 이동시키고, 목표를 만족하면 시작점을 이동하여 가능한 한 부분 수열의 길이를 최소화합니다.

 

알고리즘 흐름

1. 입력값 읽기: 배열의 크기 N과 목표 합 S를 입력받고, 배열을 초기화합니다.
2. 슬라이딩 윈도우 설정: 두 포인터 s (시작)와 e (끝)를 사용하여 부분 수열의 합을 조정합니다.
3. 조건 체크:
   • 현재 부분 수열의 합이 S보다 작으면 끝 포인터 e를 증가시켜 합을 늘립니다.
   • 현재 부분 수열의 합이 S 이상이면 시작 포인터 s를 증가시켜 합을 줄이며, 이때 부분 수열의 길이를 체크하여 최소값을 업데이트합니다.
4. 결과 출력: 가장 짧은 길이를 출력합니다. 조건을 만족하는 부분 수열이 없으면 0을 출력합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Main {
	
	static int N;  // 배열의 크기
	static int S;  // 목표 합

	public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
    	
    	int result = Integer.MAX_VALUE;  // 최소 길이를 저장할 변수, 초기값은 최대값
        
    	N = in.nextInt();  // 배열 크기 입력
    	S = in.nextInt();  // 목표 합 입력
    	
    	int[] arr = new int[N];  // 배열 초기화
    	
    	for (int i = 0; i < N; i++) {
    		arr[i] = in.nextInt();  // 배열 요소 입력
    	}
    	
    	int s = 0;  // 시작 포인터
    	int e = 0;  // 끝 포인터
    	int sum = arr[0];  // 현재 부분 수열의 합 초기화

    	while (s < N) {
    		
    		if (sum < S && e + 1 < N) {  // 합이 S보다 작고, 끝 포인터가 배열 범위 내일 때
    			e++;  // 끝 포인터 증가
    			sum += arr[e];  // 새로운 요소를 합에 추가
    		}
    		
    		else if (sum < S && e + 1 == N) {  // 합이 S보다 작고, 끝 포인터가 배열의 끝일 때
    			break;  // 더 이상 진행할 수 없음
    		}
    		
    		else if (sum >= S) {  // 합이 S 이상일 때
    			result = Math.min(result, e - s + 1);  // 현재 부분 수열 길이를 최소값으로 업데이트
    			sum -= arr[s];  // 시작 포인터의 요소를 빼서 합을 줄임
    			s++;  // 시작 포인터 증가
    		}
    	}
    	
    	if (result == Integer.MAX_VALUE) {  // 조건을 만족하는 부분 수열이 없을 경우
    		System.out.println(0);
    	} else {
    		System.out.println(result);  // 가장 짧은 부분 수열의 길이 출력
    	}
	}
}