문제
앞서풀었던 두 수의 합과 같은 투포인터를 이용하는 문제이고 난이도는 골드4로 더 높은 문제이다.
문제 설명
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
문제분석
수열이 주어질때 연속된 부분합이 S이상을 만족하는 부분합 중 가장 짧은 길이를 구해야한다.
만약 S=13이며 수열이 {5, 2, 3, 4, 10, 4, 13}일때 가장짧은길이는 1이된다.
또한 수열이 {5, 2, 3, 3, 9, 2, 1}이 라면 가장짧은 길이는 3이된다.
해결방법
먼저 떠오른 방법은 2중 for문을 사용한 방법이였지만 먼저 두 수의 합을 풀면서 비슷하게 했다가 시간초과가 났기에 굳이 구현을 하지는 않았다.
해결방법은 투포인터가 무엇인지 찾아보다가 예시로 부분합을 들길래 그냥 해당방식 구현해서 해결했다.
구현 방법을 설명하면 다음과 같다
1. start와 end를 시작지점으로 설정한다.
2.부분합이 S이상이면 start를 1증가시키고 S보다 작으면 end를 1증가시킨다.
3. 2를 start가 끝까지 갈때 까지 반복한다.
기본적인 방법은 위와 같이 구현하였고 나머지 부분은 문제에 맞도록 구현하였다.
나머지를 설명하면 부분합은 for문을 쓰면 또 시간초과 뜰거 같았다.
그래서 다른방법을 썻는데 일단 초기에 부분합을 v[0]으로 초기화 한 후 start, end의 변화에따라 값을 더하거나 빼주었다.
또한 연산을 줄이기 위하여 최소길이가 1이면 반복을 멈추도록 구현하였다.
실패한코드
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, S;
cin >> N >> S;
vector<int>v(N);
for (int i = 0; i < N; i++)
{
int n;
cin >> n;
v[i] = n;
}
int min = 200000;
int start = 0;
int end = 0;
int sum = v[0];
while (start < N)
{
if (sum >= S)
{
min = (end - start + 1) < min ? (end - start + 1) : min;
if (min == 1) break;
else sum -= v[start++];
}
else {
sum += v[++end];
}
}
if (min == 200000) cout << 0;
else cout << min;
}위의 코드를 visual studio에서 실행해봤는데 vector subscript out of range 오류가 발생했다.
대충 벡터에 범위 밖의 값을 참조했다는 의미인데 위의 코드에서 end의 값에 제한을 주지않아 벡터의 크기 이상으로 값이 커져 생긴 문제이다.
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, S;
cin >> N >> S;
vector<int>v(N);
for (int i = 0; i < N; i++)
{
int n;
cin >> n;
v[i] = n;
}
int min = 200000;
int start = 0;
int end = 0;
int sum = v[0];
while (start < N)
{
if (sum >= S)
{
min = (end - start + 1) < min ? (end - start + 1) : min;
if (min == 1) break;
else sum -= v[start++];
}
else {
if (end < N - 1) sum += v[++end];
else sum -= v[start++];
}
}
if (min == 200000) cout << 0;
else cout << min;
}위의 코드처럼 수정했고 성공했다.
+
제출을 하고 부분합이 S보다 작을때 end가 더이상 커질수가 없으면 부분합은 계속 감소하기 때문에 더이상 확인할 필요가 없으므로 연산을 줄일 수 있을것 같아 이를 적용해보았다.
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, S;
cin >> N >> S;
vector<int>v(N);
for (int i = 0; i < N; i++)
{
int n;
cin >> n;
v[i] = n;
}
int min = 200000;
int start = 0;
int end = 0;
int sum = v[0];
while (start < N)
{
if (sum >= S)
{
min = (end - start + 1) < min ? (end - start + 1) : min;
if (min == 1) break;
else sum -= v[start++];
}
else {
if (end < N - 1) sum += v[++end];
else break;
}
}
if (min == 200000) cout << 0;
else cout << min;
}
..........차이 없다😑
