본문 바로가기
Algorithm/C++

[백준 1806] 부분합

by imagineer_jinny 2022. 11. 1.

1806번: 부분합 (acmicpc.net)

 

1806번: 부분합

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

www.acmicpc.net

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int n, s, tot;
int a[100005];
int mn = 0x7fffffff;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> s;
  for(int i = 0; i < n; i++) cin >> a[i];
  tot = a[0];
  int en = 0;
  for(int st = 0; st < n; st++){
    while(en < n && tot < s){
      en++;
      if(en != n) tot += a[en];
    }
    if(en == n) break; // en이 범위를 벗어날시 종료
    mn = min(mn, en - st + 1);
    tot -= a[st];
  }
  if(mn == 0x7fffffff) mn = 0;
  cout << mn;
}

'Algorithm > C++' 카테고리의 다른 글

[백준 1920] 수 찾기  (0) 2022.11.01
[백준 2003] 수들의 합 2  (0) 2022.11.01
[백준 2230] 수 고르기  (0) 2022.11.01
[백준 14888] 연산자 끼워넣기  (0) 2022.10.20
[백준 1789] 수들의 합  (0) 2022.10.18

댓글