[C++][백준 14246] K보다 큰 구간

문제

접근 방법

자연수이기에 k보다 큰 특정 구간이 정해지면 우측에 존재하는 모든 값은 확인할 필요 없이 k보다 큰 특정 구간이다.

그렇기에 k보다 큰 특정 구간을 찾아주면서 우측의 가능한 경우까지 더해주면 모든 경우를 확인하지 않아도 되는 것이다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> nums;
int n, k, l, r;
long long answer, sum;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n;
    nums = vector<int>(n);
    for (int &num : nums)
    {
        cin >> num;
    }
    cin >> k;

    while (true)
    {
        if (sum > k) // 합이 k보다 큰 경우
        {
            answer += n - r + 1;
            sum -= nums[l++];
            if (l > n) // 범위를 벗어난 경우
            {
                break;
            }
        }
        else
        {
            sum += nums[r++];
            if (r > n) // 범위를 벗어난 경우
            {
                break;
            }
        }
    }
    cout << answer;
    return 0;
}

풀이

순위권이어서 기록해 본다.

투 포인터를 활용한 문제이다.
합이 k보다 큰 경우에는 가능한 쌍의 개수를 더해주고 왼쪽을 줄여서 값을 줄여준다.
합이 k 이하인 경우에는 값을 늘려줘야 한다.

반복하다 범위를 벗어나면 불가능하다는 뜻이므로 반복문을 나가주면 된다.