https://www.acmicpc.net/problem/1644


n이하의 소수를 모두 구해놓고 투포인터를 적용해주면 된다.


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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
using namespace std;
int n, prime[4000000], num = 1;
 
void findPrime() {
    prime[0] = 2;
    
    for (int i = 3; i <= n; i++) {
        bool isPrime = true;
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }    
        }
        if (isPrime) prime[num++] = i;
    }
}
int main(void) {
    cin >> n;
    findPrime();
    
    int cnt = 0, low = 0, high = 0;
    long long Sum = prime[0];
    while (1) {
        if (high >= num) break;
        
        if (Sum < n) {
            Sum += prime[++high];
        }
        else if (Sum == n) {
            cnt++;
            Sum += prime[++high];
        }
        else {
            Sum -= prime[low++];
            if (low > high) {
                if (prime[high] >= n) break;
                else {
                    high = low;
                    Sum = prime[high];
                }
            }
        }
    }
    cout << cnt;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29

https://www.acmicpc.net/problem/2003



n이 10000 이하이고, 시간 제한이 0.5초이기 때문에, n^2 풀이로 풀게 되면 시간 초과가 날 것이다.


따라서 O(n)에 해결할 수 있도록 투포인터를 사용하도록 한다.



초기에 st와 en을 모두 시작점으로 정해두고, en이 범위 밖으로 벗어날 때까지 진행해준다.



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
31
32
33
34
35
36
#include<iostream>
 
using namespace std;
int n, m, arr[10001];
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    int st = 0, en = 0, cnt = 0;
    long long Sum = arr[0];
 
    while (1) {
        //합이 부족해서 en이 우측으로 움직이는 건데, en이 밖으로 나갔다는 것은 더 볼 필요가 없다는 것
        //st가 우측으로 움직여봤자 합은 더 감소하기 때문에
        if (en >= n) break; 
        
        if (Sum == m) {
            Sum += arr[++en]; //딱 만족할 때 en 증가
            cnt++;
        }
 
        else if (Sum < m) Sum += arr[++en];
 
        else {
            
            Sum -= arr[st++];
            if (st > en) {
                en = st;
                Sum = arr[en];
            }
        }
    }
    cout << cnt;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28

https://www.acmicpc.net/problem/1806



투포인터를 활용해주면 된다.


길이를 언제 갱신하고, 무한루프를 어느 위치에서 종료할 것인지만 명확히 해준다면 무리없이 풀리는 문제이다.


현재까지 더한 구간합이, 넘겨야할 합보다 크다면 일단 그 시점의 길이가 최소 길이인지 비교해서 갱신해준다.


이후 왼쪽 인덱스 포인터를 증가시키고 길이를 감소시키고, 변화된 상태가 조건을 만족하는지 확인해주고 이런 흐름이다.


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
31
32
33
34
35
36
37
#include<iostream>
 
using namespace std;
typedef long long ll;
const int INF = 1000000;
int main(void) {
    ll arr[100001];
    double s;
    int n;
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    int l = 0, h = 0, len = 0, Min = INF;
    ll Sum = 0;
    while (1) {
        if (Sum < s) {
            if (h > n - 1) break; //h가 n인데, 쿼리를 실행하게 하면 안된다
            Sum += arr[h];
            h++;
            len++;
        }
        else {
            if (len < Min) Min = len;
            
            Sum -= arr[l];
            l++; 
            len--;
        }
    }
    if (Min != INF)
        cout << Min << '\n';
    else
        cout << 0 << '\n';
    
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 10254 고속도로 C++  (0) 2019.08.17
백준 2458 키 순서 C++  (0) 2019.08.16
백준 11404 플로이드 C++  (0) 2019.08.16
백준 11657 타임머신 C++  (0) 2019.08.16
백준 1753 최단경로 C++  (0) 2019.08.15

+ Recent posts

티스토리툴바