링크
https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
풀이 과정
투포인터로 풀면 O(n)시간 안에 풀리는 문제이다.
다만 유의해야할점은
4 4
1 5 2 2
와 같은 예시에서 5지점에서 포인터가 역전될수도 있으므로 단순히 high>=low를 반복조건으로 두면 틀리게 된다.
따라서 포인터가 역전당했을때 다시 포인터를 옮겨주거나, 혹은 조건에서 high>=low를 제거하면 된다.
코드
#include <iostream>
using namespace std;
int main()
{
long n,m;
int l=0;
int arr[100000];
cin >> n;
cin >> m;
int r = 0;
for (int i = 0; i < n; i++)cin >> arr[i];
int cnt = 0;
int sum = arr[0];
while (r >= l && r < n) {
if (sum== m) {
cnt++;
sum += arr[++r];
}
else if (sum > m) {
sum -= arr[l++];
if (l > r) {
r = l;
sum = arr[r];
}
}
else {
sum += arr[++r];
}
}
cout << cnt;
}
'Koala - 5기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/C++] 알고리즘 1644번 소수의 연속합 (1) | 2022.01.31 |
---|---|
[BOJ / Python] 1644 - 소수의 연속합 (0) | 2022.01.31 |
[BOJ / Python] 2467번: 용액 (0) | 2022.01.31 |
BOJ 1644(python) : 소수의 연속합 (0) | 2022.01.31 |
[BOJ / C++] 14465 : 소가 길을 건너간 이유 5 (0) | 2022.01.30 |
링크
https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
풀이 과정
투포인터로 풀면 O(n)시간 안에 풀리는 문제이다.
다만 유의해야할점은
4 4
1 5 2 2
와 같은 예시에서 5지점에서 포인터가 역전될수도 있으므로 단순히 high>=low를 반복조건으로 두면 틀리게 된다.
따라서 포인터가 역전당했을때 다시 포인터를 옮겨주거나, 혹은 조건에서 high>=low를 제거하면 된다.
코드
#include <iostream>
using namespace std;
int main()
{
long n,m;
int l=0;
int arr[100000];
cin >> n;
cin >> m;
int r = 0;
for (int i = 0; i < n; i++)cin >> arr[i];
int cnt = 0;
int sum = arr[0];
while (r >= l && r < n) {
if (sum== m) {
cnt++;
sum += arr[++r];
}
else if (sum > m) {
sum -= arr[l++];
if (l > r) {
r = l;
sum = arr[r];
}
}
else {
sum += arr[++r];
}
}
cout << cnt;
}
'Koala - 5기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/C++] 알고리즘 1644번 소수의 연속합 (1) | 2022.01.31 |
---|---|
[BOJ / Python] 1644 - 소수의 연속합 (0) | 2022.01.31 |
[BOJ / Python] 2467번: 용액 (0) | 2022.01.31 |
BOJ 1644(python) : 소수의 연속합 (0) | 2022.01.31 |
[BOJ / C++] 14465 : 소가 길을 건너간 이유 5 (0) | 2022.01.30 |