반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. Prefix Sum :: http://www.crocus.co.kr/259

2. 투 포인터


http://www.crocus.co.kr/595 (1806번 부분합) 문제와 상당히 유사한 문제이다.


다른 점이라고는 소수를 배열에 넣어줘야 한다는 것이고 그 외에는 방식이 모두 같다.


투 포인터에 대해 이해를 하고, 그에 맞게 p1와 p2를 조작할 수 있다면 해결할 수 있는 문제이다.


자세한 내용은 주석을 통해 달아두었다.






소스 코드 : 


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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <math.h>
 
#define MAX_N 4000001
 
using namespace std;
 
unsigned char sieve[(MAX_N + 7) / 8];
int pSum[MAX_N];
 
// K가 소수인지 확인한다.
inline bool isPrime(int k)
{
    return sieve[k >> 3] & (1 << (k & 7));
}
 
// k가 소수가 아니라고 표시한다.
inline void setComposite(int k)
{
    sieve[k >> 3] &= ~(1 << (k & 7));
}
 
// 비트 마스크를 사용하는 에라토스테네스의 체의 구현
// 이 함수를 수행하고 난 뒤, isPrime()을 이용해 각 수가 소수인지 알 수 있다.
void eratosthenes(int n)
{
    memset(sieve, 255, sizeof(sieve));
    setComposite(0);
    setComposite(1);
 
    int sqrtn = int(sqrt(n));
    for (int i = 2; i <= sqrtn; ++i)
        // 이 수가 아직 지워지지 않았다면
        if (isPrime(i))
            // i의 배수 j들에 대해 isPrime[i] = false로 둔다.
            // i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.
            for (int j = i*i; j <= n; j += i)
                setComposite(j);
}
 
int main()
{
    int n, p1 = 0, p2 = 1;
    int ans = 0;
    int cnt = 0;
    int size;
 
    scanf("%d", &n);
    eratosthenes(n);
 
    // 소수의 부분 합을 구한다.
    while (p1 <= n)
    {
        if (isPrime(p1))
        {
            pSum[p2] = pSum[p2 - 1] + p1;
            p2++;
        }
            
        p1++;
    }
 
    size = p2 - 1;
 
    p1 = 1;
    p2 = 1;
 
    // p1이 오버 플로우 되는 경우 break
    while (!(p1 > size && p1 > p2))
    {
        // p1~p2까지 합이 n과 같으면
        if (pSum[p2] - pSum[p1 - 1] == n)
        {
            cnt++;
            // p1 == p2면 p2 증가
            if (p1 == p2)
                p2++;
            
            // 그외는 p1 증가
            else
                p1++;
        }
 
        // p1~p2까지 합이 n보다 작으면
        else if (pSum[p2] - pSum[p1 - 1] < n)
        {
            // p2가 아직 끝점 도달하지 못했을 경우 p2 증가
            if (p2 < size)
                p2++;
 
            // 그외 p1 증가
            else
                p1++;
        }
 
        // p1~p2까지 합이 n보다 크면
        else
        {
                // p1을 증가시켜보고 부분합을 검사한다.
                p1++;
 
                if (pSum[p2] - pSum[p1 - 1] == n)
                {
                    cnt++;
                    p1++;
                }
        }
        
    }
    
    cout << cnt;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지 (새창열림)

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[3078번] 좋은 친구  (1) 2017.02.16
[2096번] 내려가기  (0) 2017.02.14
[1806번] 부분합  (0) 2017.02.13
[2581번] 소수  (0) 2017.02.13
[11377번] 열혈강호 3  (4) 2017.02.10

티스토리툴바