백준 1806

ALGORITHM
2025-09-17

부분합

관련 개념

#투포인터 #부분합

문제

1806

📌 1 단계 : 문제 분석하기

  • ‘연속된’ 그리고 ‘누적합’이라는 말에 집중해야 한다.
  • 이러한 키워드가 있을 때는 슬라이딩 윈도우 혹은 투포인터를 활용해야 한다!

📌 2 단계 : 손으로 풀어보기

  • 현재의 합이 S보다 작다면 end_index를 증가한다
  • 현재의 합이 S보다 크거나 같다면, 요소의 개수를 세고, 최솟값을 갱신한 후, start_index를 증가한다.

📌 3 단계 : 슈도 코드 작성하기

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <numeric>
#include <algorithm> 
#include <set>
 
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int N;
	long long S; 
	cin >> N >> S;
 
	vector<int> arr(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
 
	int ans = INT_MAX;
	long long current_sum = 0;
	int start_index = 0;
 
	// end_index를 0부터 N-1까지 이동시키며 창문을 오른쪽으로 확장
	for (int end_index = 0; end_index < N; end_index++) {
 
		// 1. 현재 end_index의 원소를 더함 (창문 확장)
		current_sum += arr[end_index];
 
		// 2. 합이 S 이상이면, 조건을 만족하는 가장 짧은 길이를 찾기 위해
		//    start_index를 오른쪽으로 이동시키며 창문을 축소
		while (current_sum >= S) {
			// 현재 길이를 계산하고, 최소 길이(ans)를 갱신
			ans = min(ans, end_index - start_index + 1);
 
			// 창문을 왼쪽에서부터 줄이기 위해 start_index의 값을 빼고, start_index를 1 증가
			current_sum -= arr[start_index];
			start_index++;
		}
	}
 
	// 만약 ans가 초기값(INT_MAX) 그대로라면, 합을 S 이상으로 만드는 부분 배열이 없는 것
	if (ans == INT_MAX) {
		cout << 0;
	}
	else {
		cout << ans;
	}
 
	return 0;
}

📌 5 단계 : 배운점

  • 골드4 치고 쉬운 것 같다. (조금 성장했을지도)
  • 문제에 힌트가 너무 명백하게 드러나 있다.
  • 처음에는 큐를 사용했는데, 생각해보니 굳이 큐를 사용할 필요는 없었다.