[BOJ] 싫은데요 - Compy's Blog

싫은데요

TimeLimit	MemoryLimit	Condition	TAG
1s	1024MB	(1 ≤ N ≤ 500,000 1 ≤ M, A_i ≤ 1e9 )	Two Pointer

범위를 슬라이싱 해야되는데 N이 5*10^5거든요? O(N^2)이 1초에 절대 안 돌아가기 때문에 다른 방법을 생각해야 했고.. 그게 바로 “투 포인터” 였습니다. 그래서 그냥 전형적인 같은 시작 투포인터를 이용하면 됩니당

정답 코드

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;


int nums[500002];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    
    cin >> n >> m;
    
    
    
    for(int i = 1; i <= n; i++){
        cin >> nums[i];
    }
    
    int left = 1, right = 1;
    
    
    
    ll current = nums[1];
    ll result = 0;
    while(right <= n){
        if(right < left){
            right++;
            current += nums[right];
        }
        
        if(current <= m){
            result = max(result, current);
            right++;
            current += nums[right];
        }else{
            current-=nums[left];
            left++;
        }

    }
        
    cout << result;
    
    return 0;
}