✔ 문제해결전략
- Two Pointer
- 1<=N<=100000이므로 완전탐색(O(N^2)) 불가능
✔ 해결과정
- BOJ: 2230: 수 고르기 와 비슷하다. end가 가리키는 값을 sum에 반영하고 mini 값을 업데이트해야 하는데 end를 업데이트하기 직전에 sum 값에 반영하고 end를 업데이트하여서 처음에 오답이 나왔다. end가 가리키는 값을 먼저 sum에 반영하니 되었다.
#include <bits/stdc++.h>
using namespace std;
int arr[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, s, mini = 0x7fffffff;
cin >> n >> s;
for(int i=0;i<n;i++) {
cin >> arr[i];
}
int front = 0, end = 0, sum = 0;
for(int front=0;front<n;front++) {
while(end<n && sum < s) {
sum += arr[end];
end++;
}
if(end==n) break;
if(sum >= s) {
mini = min(end-front+1, mini);
}
sum -= arr[front];
}
if(mini==0x7fffffff) cout << 0;
else cout << mini;
}
#include <bits/stdc++.h>
using namespace std;
int arr[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, s, mini = 0x7fffffff;
cin >> n >> s;
for(int i=0;i<n;i++) {
cin >> arr[i];
}
int front = 0, end = 0, sum = arr[0];
for(int front=0;front<n;front++) {
while(end<n && sum<s) {
end++;
sum += arr[end];
}
if(end==n) break;
if(sum >= s) {
mini = min(end-front+1, mini);
}
sum -= arr[front];
}
if(mini==0x7fffffff) cout << 0;
else cout << mini;
}
기존에 풀어본 two pointer 문제들과 다르게 이 문제는 정렬을 하지 않고 바로 진행한다. 그래서 binary search로는 풀이가 불가능하다.
바킹독님 감사합니다