백준 1806 부분합 풀이 (Two-pointer)
문제
https://www.acmicpc.net/problem/1806
문제내용
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
예제 입력 1
10 15
5 1 3 5 10 7 4 9 2 8
예제 입력 2
2
문제풀이
문제해설
- 연속된 수의 부분합 중 S 이상이 되는 것중, 가장 짧은 것의 길이를 구하는 문제이다.
- 연속된 수의 부분합은 주어진 수열에서 연속된 몇 개의 수를 더한 값을 의미
- 모든 수를 비교하기 위해 2중 for문을 사용하면 시간 초과가 발생할 수 있기 때문에 투 포인터 알고리즘을 이용해서 해결한다.
코드 설명1
#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v; // 길이가 N인 수열
int N; // 수열의 길이
int S; // 부분합보다 같거나 같은 수
int start = 0; // 포인트 시작점
int end = 0; // 포인트 끝점
int sum = 0; // 부분합
int result = INT_MAX; // 최소 길이
// ~중략~
}
- 필요한 헤더를 추가하고, 변수를 선언한다.
코드 설명2
while (start <= end) {
if (sum >= S) {
result = min(result, end - start);
sum -= v[start++];
}
else if (end == N) break;
else {
sum += v[end++];
}
}
- start가 end를 넘지 않을 동안 while문을 반복한다.
- 만약 sum이 s보다 이상이면 현재 최소 길이와 비교해서 result에 저장한다. 그리고 start 포인터를 1증가시킨다. (sum 값 감소)
- end가 N과 같이지면 반복문을 끝낸다.
- 만약 sum이 s보다 미만이면 두 포인터의 범위를 넓혀야 하므로 end 포인터를 1증가시킨다. (sum 값 증가)
그림 예시
다음 예시는 N= 10, S=15이고, 수열은 [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]일 경우이다.
- start =0, end = 0 0이기 때문에 while문을 반복한다.
- sum = 0이기 때문에 end에 위치한 값을 sum에 더하고, end 포인터를 1증가시킨다.
- result = INT_MAX, start = 0, sum = 5, end = 1
- start = 0, end = 1이기 때문에 while문을 반복한다.
- sum = 5이기 때문에 end에 위치한 값을 sum에 더하고, end 포인터를 1증가시킨다.
- result = INT_MAX, start = 0, sum = 6, end = 2
- start = 0, end = 2이기 때문에 while문을 반복한다.
- sum = 6이기 때문에 end에 위치한 값을 sum에 더하고, end 포인터를 1증가키신다.
- result = INT_MAX, start = 0, sum = 9, end = 3
- start = 0, end = 3이기 때문에 while문을 반복한다.
- sum = 9이기 때문에 end에 위치한 값을 sum에 더하고, end 포인터를 1증가키신다.
- result = INT_MAX, start = 0, sum = 14, end = 4
- start = 0, end = 4이기 때문에 while문을 반복한다.
- sum = 14이기 때문에 end에 위치한 값을 sum에 더하고, end 포인터를 1증가키신다.
- result = INT_MAX, start = 0, sum = 24, end = 5
- start = 0, end = 5이기 때문에 while문을 반복한다.
- sum = 24이기 때문에 최소 길이를 구하고, start에 위치한 값을 sum에 뺀다. 그리고 start 포인터를 1증가시킨다.
- result = 5, start = 1, sum = 19, end = 5
- start = 1, end = 5이기 때문에 while문을 반복한다.
- sum = 19이기 때문에 최소 길이를 구하고, start에 위치한 값을 sum에 뺀다. 그리고 start 포인터를 1증가시킨다.
- result = 4, start = 2, sum = 18, end = 5
- start = 2, end = 5이기 때문에 while문을 반복한다.
- sum = 18이기 때문에 최소 길이를 구하고, start에 위치한 값을 sum에 뺀다. 그리고 start 포인터를 1증가시킨다.
- result = 3, start = 3, sum = 15, end = 5
- start = 3, end = 5이기 때문에 while문을 반복한다.
- sum = 15이기 때문에 최소 길이를 구하고, start에 위치한 값을 sum에 뺀다. 그리고 start 포인터를 1증가시킨다.
- result = 2, start 4, sum = 10, end = 5
- start = 4, end = 5이기 때문에 while문을 반복한다.
- sum = 10이기 때문에 end에 위치한 값을 sum에 더하고, end 포인터를 1증가키신다.
- result = 2, start 4, sum = 17, end = 6
- 이 과정을 end가 N이 될 때까지 같은 방식으로 진행
전체코드
#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v; // 길이가 N인 수열
int N; // 수열의 길이
int S; // 부분합보다 같거나 같은 수
int start = 0; // 포인트 시작점
int end = 0; // 포인트 끝점
int sum = 0; // 부분합
int result = INT_MAX; // 최소 길이
// 데이터 입력
cin >> N >> S;
if (N < 10 || N>100000) return 0;
if (S < 0 || S>100000000) return 0;
// 수열 원소 입력
for (int i = 0; i < N; i++) {
int a;
cin >> a;
v.push_back(a);
}
while (start <= end) {
if (sum >= S) {
result = min(result, end - start);
sum -= v[start++];
}
else if (end == N) break;
else {
sum += v[end++];
}
}
if (result == INT_MAX) cout << 0;
else cout << result;
return 0;
}