티스토리 뷰
728x90
https://www.acmicpc.net/problem/2003
투포인터 C++
대략 25분
수열의 부분합 중 M을 만족시키는 경우의 수를 출력하는 문제이다
접근방법
투포인터를 사용해서 합이 M보다 작으면 -> end를 오른쪽으로 이동시키고
크면 -> start를 오른쪽으로 이동시킨다.
M과 같으면 경우의 수(cnt)를 1증가시키면서 end를 오른쪽으로 이동시킨다.
오답노트
구간의 합이 M보다 큰 경우 중 start와 end가 같은 점을 가리키고 있을때
그대로 start를 오른쪽으로 이동시키면 end보다 커져서 반복문을 나가게 된다.
그래서 1 2 1 과 같은 케이스에서 뒤에 1을 보지 못하고 2에서 반복문이 종료된다.
따라서 합이 M보다 클 때 start와 end가 같은 점을 가리키고 있으면 end를 오른쪽으로 이동시키고
start와 end가 다른 점을 가리키고 있으면 start를 오른쪽으로 이동시키면 된다.
이 예외는 수열 중 하나의 숫자가 M보다 클때 발생하는 예외이다.
나는 if문으로 따로 처리해줬는데 더 나은 로직이 있는지 모르겠다.
소스코드
#include <iostream>
using namespace std;
int main(){
//input
int N, target;
cin >> N >> target;
int arr[N+1];
for(int i = 0 ; i < N ; i++){
cin >> arr[i];
}
//process
int s,e;
s = e = 0;
int sum = arr[0];
int cnt = 0;
while(s <= e && e < N){
if(sum > target){
if(s == e){
sum += arr[++e];
}else{
sum -= arr[s++];
}
}else if(sum < target){
sum += arr[++e];
}else{
cnt++;
sum += arr[++e];
}
}
//output
cout << cnt << "\n";
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 11728] 알고리즘 108일차 : 배열 합치기 (0) | 2021.07.23 |
---|---|
[백준 1406] 알고리즘 107일차 : 에디터 (0) | 2021.07.22 |
[백준 1806] 알고리즘 105일차 : 부분합 (0) | 2021.07.19 |
[백준 1655] 알고리즘 104일차 : 가운데를 말해요 (0) | 2021.07.12 |
[백준 10866] 알고리즘 103일차 : 덱 (0) | 2021.07.09 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 트리
- 가장 큰 수 Swift
- 수학
- 가장 큰 수 프로그래머스
- BFS
- 프로그래머스
- 파이썬
- 정렬
- 알고리즘
- 다이나믹프로그래밍
- 투포인터
- 동적계획법
- 토마토
- dfs
- 백준
- 최단경로
- 스택
- 이분탐색
- 최소힙
- 게임이론
- 웹크롤링
- 백트래킹
- 우선순위큐
- c++
- 브루트포스
- 자바
- Swift
- 최대힙
- 그리디알고리즘
- dp
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
글 보관함