[백준] 1806번 부분합
백준 1806번 부분합 문제 풀이
문제 설명
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
문제를 보고 든 생각
- 투 포인터를 사용하면 되겠다.
- 합이 클 수 있으니 unsigned long long 타입을 사용하자
풀이 간단 설명
- lp, rp 모두 0에서 시작해서 합이 S 이상이 될 때 까지 rp를 증가시킨다.
- 합이 S 미만이 될 때 까지 lp를 증가시킨다.
- 1과 2를 하는 동안 간격의 최솟값을 저장한다.
코드
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;
ull N, S;
vector<ull> v;
void getInput(){
cin >> N >> S;
int n = N;
while(n--){
ull temp; cin >> temp;
v.push_back(temp);
}
}
void solve(){
getInput();
ull lp=0, rp=0;
ull sumNum = 0;
ull sumLen = 100000001;
while(rp < N){
sumNum += v[rp];
if(sumNum >= S){
ull diffLen = rp - lp + 1;
if(sumLen > diffLen){
sumLen = diffLen;
}
sumNum -= v[lp++];
sumNum -= v[rp];
continue;
}
++rp;
}
if(sumLen == 100000001){
cout << 0;
} else{
cout << sumLen;
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
Author And Source
이 문제에 관하여([백준] 1806번 부분합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kkoma2623/백준-1806번-부분합
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
- 투 포인터를 사용하면 되겠다.
- 합이 클 수 있으니 unsigned long long 타입을 사용하자
풀이 간단 설명
- lp, rp 모두 0에서 시작해서 합이 S 이상이 될 때 까지 rp를 증가시킨다.
- 합이 S 미만이 될 때 까지 lp를 증가시킨다.
- 1과 2를 하는 동안 간격의 최솟값을 저장한다.
코드
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;
ull N, S;
vector<ull> v;
void getInput(){
cin >> N >> S;
int n = N;
while(n--){
ull temp; cin >> temp;
v.push_back(temp);
}
}
void solve(){
getInput();
ull lp=0, rp=0;
ull sumNum = 0;
ull sumLen = 100000001;
while(rp < N){
sumNum += v[rp];
if(sumNum >= S){
ull diffLen = rp - lp + 1;
if(sumLen > diffLen){
sumLen = diffLen;
}
sumNum -= v[lp++];
sumNum -= v[rp];
continue;
}
++rp;
}
if(sumLen == 100000001){
cout << 0;
} else{
cout << sumLen;
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
Author And Source
이 문제에 관하여([백준] 1806번 부분합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kkoma2623/백준-1806번-부분합
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- lp, rp 모두 0에서 시작해서 합이 S 이상이 될 때 까지 rp를 증가시킨다.
- 합이 S 미만이 될 때 까지 lp를 증가시킨다.
- 1과 2를 하는 동안 간격의 최솟값을 저장한다.
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;
ull N, S;
vector<ull> v;
void getInput(){
cin >> N >> S;
int n = N;
while(n--){
ull temp; cin >> temp;
v.push_back(temp);
}
}
void solve(){
getInput();
ull lp=0, rp=0;
ull sumNum = 0;
ull sumLen = 100000001;
while(rp < N){
sumNum += v[rp];
if(sumNum >= S){
ull diffLen = rp - lp + 1;
if(sumLen > diffLen){
sumLen = diffLen;
}
sumNum -= v[lp++];
sumNum -= v[rp];
continue;
}
++rp;
}
if(sumLen == 100000001){
cout << 0;
} else{
cout << sumLen;
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
Author And Source
이 문제에 관하여([백준] 1806번 부분합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kkoma2623/백준-1806번-부분합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)