티스토리 뷰

728x90

문제 링크

www.acmicpc.net/problem/1806

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

 

풀이

모든 수가 자연수입니다.

i, j를 적당히 움직여서 합의 최댓값과 그때의 수열 길이를 구해줍시다.

 

 

정답 코드

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int n, s;
int p[111'111];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    int sum = 0;
    int ans = INF;
    for (int i = 0, j = 0; i < n && j <= n;) {
        if (j < n && sum < s) {
            sum += p[j++];
        } else {
            sum -= p[i++];
        }
        if (sum >= s) ans = min(ans, j - i);
    }
    if (ans == INF) ans = 0;
    cout << ans;
}
728x90

'알고리즘 > 문제 풀이' 카테고리의 다른 글

[BOJ] 백준 2143 두 배열의 합  (0) 2021.03.08
[BOJ] 백준 1987 알파벳  (0) 2021.03.08
[BOJ] 백준 1799 비숍  (0) 2021.03.08
[BOJ] 백준 1647 도시 분할 계획  (0) 2021.03.08
[BOJ] 백준 1644 소수의 연속합  (0) 2021.03.08
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함