[백준/C++] 1806번. 부분합
1. 문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
3. 출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
4. 풀이
투 포인터문제start와end두 개의 포인터를 조작해서 답을 찾는다.start부터end까지 합이 원하는 결과보다 작다면end를 증가시킨다.start부터end까지 합을 구할 때 갱신할 때마다 새로 더하지 말고 현재의 합계를 저장해놓고start에 해당하는 값을 빼거나end에 해당하는 값을 더하는 식으로 진행하는 게 효율적이다.- 주의할 점은
start를 증가시킬 때는 해당하는 값을 먼저 빼고 인덱스를 증가시켜야 하고end는 인덱스를 증가시키고 값을 더해야 한다.
start부터end까지 합이 원하는 결과 이상이면 현재 길이를 저장한다.- 현재 길이가 최솟값일 때만 결과를 갱신한다.
start나end중 하나가 배열의 범위를 벗어나면 반복문을 종료한다.
5. 처음 코드와 달라진 점
- 부분합이 이상인 것을 일치로 봐서 코드를 수정했다.
result값을n으로 초기화했는데 이러면 답을 찾았는지 아닌지 확인할 방법이 없어서boolean타입 변수findAnswer를 추가해주었다.findAnswer없이result값을n이상의 큰 값으로 지정해주어도 될 것 같다.
6-1. 코드(findAnswer 有)
#include <iostream>
#include <algorithm>
using namespace std;
int n, target;
int arr[100000];
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> target;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int start = 0, end =0;
int sum = arr[start];
int result = n;
bool findAnswer = false;
while (start < n && end < n) {
if (target <= sum) {
findAnswer = true;
result = min(result, end - start + 1);
sum -= arr[start];
start++;
}
else {
end++;
sum += arr[end];
}
}
if (!findAnswer) cout << 0;
else cout << result;
}6-2. 코드 (INF 이용)
#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;
int n, target;
int arr[100000];
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> target;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int start = 0, end =0;
int sum = arr[start];
int result = INF;
while (start < n && end < n) {
if (target <= sum) {
result = min(result, end - start + 1);
sum -= arr[start];
start++;
}
else {
end++;
sum += arr[end];
}
}
if (result == INF) cout << 0;
else cout << result;
}21.10.11 추가
풀이
- 기본 풀이는 같지만 while-loop에서 for-loop로 변경하였다.
- answer 변수를
INF값으로 초기화한다. - 반복문을 돌면서 sum 변수에 right 인덱스의 값을 추가한다.
- sum 변수의 값이 s보다 크거나 같다면 작아질 때까지 아래의 작업을 반복한다.
right - left + 1의 값과 answer 값 중 작은 값으로 answer의 값으로 갱신한다.- while 반복문을 돌면서 left에 해당하는 값을 빼준다.
- for 반복문이 끝나고 answer가 여전히 INF값이면 0으로 갱신한다.
- answer에 저장된 값을 출력한다.
코드 - CPP
#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;
int nums[100000];
int n, s;
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int answer = INF;
int sum = 0;
cin >> n >> s;
for (int i = 0; i < n; i++)
{
cin >> nums[i];
}
int left = 0;
for (int right = 0; right < n; right++)
{
sum += nums[right];
while (s <= sum)
{
answer = min(answer, right - left + 1);
sum -= nums[left++];
}
}
answer = answer == INF ? 0 : answer;
cout << answer;
}코드 - js
function solution(nums, s) {
let answer = Number.MAX_SAFE_INTEGER;
let sum = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (s <= sum) {
answer = Math.min(answer, right - left + 1);
sum -= nums[left++];
}
}
answer = answer === Number.MAX_SAFE_INTEGER ? 0 : answer;
return answer;
}