Search

BOJ 2003 수들의 합 2

태그
브루트포스 알고리즘
누적 합
두 포인터
생성일
2024/09/10 02:50

문제 설명

•
주어진 수열에서 ii번째 수부터 jj번째 수까지의 구간 합이 MM이 되는 경우의 수를 구하는 문제

예제 입력/출력

•
입력1
10 5 1 2 3 4 2 5 3 1 1 2
Plain Text
복사
•
출력1
3
Plain Text
복사

제약 조건

•
1≤N≤10,0001 ≤ N ≤ 10,000
•
1≤M≤300,000,0001 ≤ M ≤ 300,000,000
•
원소에 대한 설명
◦
1≤1 ≤ 각 원소 ≤30,000≤ 30,000

문제 풀이

접근1 브루트 포스 - O(N2)O(N^2)
접근2 파라매트릭 서치 - O(N⋅logN)O(N \cdot logN)
접근3 투 포인터 알고리즘 - O(N)O(N)

풀이 코드

접근1 브루트 포스 - O(N2)O(N^2)
접근2 파라매트릭 서치 - O(N⋅logN)O(N \cdot logN)
접근3 투 포인터 알고리즘 - O(N)O(N)