Search

BOJ 1806 부분합

태그
누적 합
두 포인터
생성일
2024/12/11 12:11

문제 설명

•
길이가 NN인 수열에 대해, 연속된 수들의 부분합이 SS 이상이면서 가장 짧은 것의 길이를 구하는 문제

예제 입력/출력

•
입력1
10 15 5 1 3 5 10 7 4 9 2 8
Plain Text
복사
•
출력1
2
Plain Text
복사

제약 조건

•
10≤N≤100,00010 ≤ N ≤ 100,000
◦
0<0 < 원소의 값 ≤10,000≤ 10,000
•
0<S≤100,000,0000 < S ≤ 100,000,000

문제 풀이

접근1 브루트 포스 - O(N2)O(N^2)
접근2 누적합 + 파라매트릭 서치 - O(N⋅logN)O(N \cdot logN)
접근3 투 포인터 - O(N)O(N)

풀이 코드

접근2 누적합 + 파라매트릭 서치 - O(N⋅logN)O(N \cdot logN)
접근3 투 포인터 - O(N)O(N)