๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/BOJ

[C++/BOJ] 1806 : ๋ถ€๋ถ„ํ•ฉ (ํˆฌํฌ์ธํ„ฐ)

728x90

https://www.acmicpc.net/problem/1806

๋ฌธ์ œ

10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ๊ธธ์ด N์งœ๋ฆฌ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜์—ด์—์„œ ์—ฐ์†๋œ ์ˆ˜๋“ค์˜ ๋ถ€๋ถ„ํ•ฉ ์ค‘์— ๊ทธ ํ•ฉ์ด S ์ด์ƒ์ด ๋˜๋Š” ๊ฒƒ ์ค‘, ๊ฐ€์žฅ ์งง์€ ๊ฒƒ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— N (10 ≤ N < 100,000)๊ณผ S (0 < S ≤ 100,000,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด์ด ์ฃผ์–ด์ง„๋‹ค. ์ˆ˜์—ด์˜ ๊ฐ ์›์†Œ๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด์ ธ ์žˆ์œผ๋ฉฐ, 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ์ตœ์†Œ์˜ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์ผ ๊ทธ๋Ÿฌํ•œ ํ•ฉ์„ ๋งŒ๋“œ๋Š” ๊ฒƒ์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด 0์„ ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค.


 

๊ณจ๋“œ4์ธ๋ฐ ๋น„๊ต์  ์‰ฌ์šด ๋ฌธ์ œ์ด๋‹ค.

๋ฌธ์ œ๋ฅผ ์ž˜ ์ฝ์ž..

s ์ด์ƒ์˜ ํ•ฉ์ด ๋‚˜์˜ค์ง€ ์•Š๋Š”๋‹ค๋ฉด 0์„ ์ถœ๋ ฅํ•˜๊ธฐ!!

 

 

 

๋‚˜์˜ ํ’€์ด

#include <iostream>
using namespace std;

int main(){
    int n;
    int s;
    int nums[100001]={0};
    int minlen = 100001;
    cin >> n >> s;
    for (int i = 0; i < n; ++i){
        cin >> nums[i];
    }
    int left = 0;
    int right = 0;
    int nowsum = nums[0];
    while(right < n){
        if (nowsum < s){
            right++;
            nowsum += nums[right];
        }
        if(nowsum >= s){
            if(minlen > right-left+1){
                minlen = right - left + 1;
            }
            nowsum -= nums[left];
            left++;
        }
    }
    if(minlen==100001) cout << 0;
    else cout << minlen;
    return 0;
}
728x90