생각
투 포인터를 사용해서 풀 수 있다.
st, en 두 포인터를 둔다.
1. 수들을 입력받아 배열에 저장한다.
2. 수의 합을 저장하는 변수 total은 arr[0]을 더 해주고, 줄의 길이를 저장하는 변수 len은 최대한 큰 수로 둔다(0x7fffffff).
3. en을 0으로 둔다.
4. en이 n보다 작고 total이 s보다 작다면 en을 한 칸 오른쪽으로 옮긴다.
5. 그러고도 en이 n보다 작다면 total에 arr[en]을 더 해준다.
6. 계속 더하다보면 total이 s보다 커진다.
7. 그러면 그 때 en-st+1이 len보다 작다면 len에 en-st+1을 저장한다.
8. st가 다음 칸으로 넘어가기 전에 total에서 arr[st]를 빼준다.
9. 만약 s보다 큰 부분합을 찾지 못했다면 0을 출력하고, 아니라면 len을 출력한다.
코드
#include <bits/stdc++.h>
using namespace std;
int arr[100005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, s;
cin >> n >> s;
for (int i = 0; i < n; i++) { // 입력
cin >> arr[i];
}
int en = 0;
int len = 0x7fffffff; // 줄의 길이를 저장하는 변수
int total = arr[0]; // 수의 합을 저장하는 변수
for (int st = 0; st < n; st++) {
while (en < n && total < s) {
en++; // en을 한 칸 오른쪽 옆으로 옮긴다
if (en != n) {
total += arr[en]; // arr[en]을 total에 더해준다
}
}
if (en == n) { // 범위를 벗어나면
break;
}
if (total >= s) { // total이 s보다 크다면
if (en - st + 1 < len) { //
len = en - st + 1;
}
}
total -= arr[st]; // st가 다음으로 넘어가기 전에 total에서 arr[st]를 뻬준다.
}
if (len == 0x7fffffff) { // s보다 큰 부분합을 찾지 못했다면
len = 0; // len에 0을 저장한다.
}
cout << len; // len 출력
}
예외처리가 중요했다. en이 n이 아닐 때 arr[en]을 total에 더해주는 부분이나, len이 0x7fffffff라면 len에 0을 저장하는 부분이 있어야 문제를 해결할 수 있다. 꼼꼼히 따져보는 습관을 들이자.
결과
'Baekjoon(C++)' 카테고리의 다른 글
[백준] 13414번: 수강신청 C++로 풀어보기 (0) | 2023.08.20 |
---|---|
[백준] 1644번: 소수의 연속합 C++로 풀어보기 (0) | 2023.08.17 |
[백준] 2230번: 수 고르기 C++로 풀어보기 (0) | 2023.08.16 |
[백준] 2805번: 나무 자르기 C++로 풀어보기 (0) | 2023.08.12 |
[백준] 1019번: 책 페이지 C++로 풀어보기 (0) | 2023.08.12 |