백준 문제 풀이 - 부분합 1806번
📜 문제 이해하기
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
💡 문제 재정의
수열의 합이 S 이상이 되는 가장 짧은 길이를 구하라.
✏️ 계획 수립
Two Pointer 기법을 쓰면 O(N)안에 문제를 해결할 수 있다.
start와 end를 0번째 인덱스에서 시작하여 만약 start와 end 사이의 값의 합이 S 이상이라면 가장 짧은 길이인지 확인한다. 그 후 S 아래가 될때까지 start를 늘리면서 부분 합을 구한다. 이 작업을 start가 end와 같아질때까지 수행하고 가장 짧은 길이를 출력하면 된다.
💻 계획 수행
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, S, sum = 0, start = 0, end = 0, min_length = 100001;
cin >> N >> S;
vector<int> num(N+1);
for (int i=0; i<N; i++) {
cin >> num[i];
}
while (true) {
if (sum >= S) {
if (end - start < min_length) min_length = end - start;
sum -= num[start];
start += 1;
}
else {
sum += num[end];
if (end < N) end += 1;
else {
sum -= num[start];
start += 1;
}
}
if (start >= end) break;
}
min_length = min_length == 100001 ? 0 : min_length;
cout << min_length;
return 0;
}
🤔 회고
이 문제를 처음엔 브루트포스로 풀었으나 해당 알고리즘은 O(N²)이라 시간초과가 발생했다. 두 포인터 알고리즘으로 문제를 해결해야 O(N)안에 문제가 해결되기에 브루트포스를 사용하면 안된다. 아래 링크는 두 포인터 알고리즘에 대한 설명이다.
https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md
Author And Source
이 문제에 관하여(백준 문제 풀이 - 부분합 1806번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@delicate1290/백준-문제-풀이-부분합-1806번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)