반응형

문제 링크: https://www.acmicpc.net/problem/1644

 

1644번: 소수의 연속합

문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한

www.acmicpc.net

<문제 풀이> 에라토스테네스의 체, 투 포인터

 

에라토스테네스의 체로 N이하의 소수를 모두 구하고 투 포인터 알고리즘으로 부분합을 구해주면 쉽게 풀 수 있습니다

 

<C++ 소스 코드>

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
#include <iostream>
#include <vector>
using namespace std;
 
bool visited[4000001];
bool is_prime[4000001];
vector<int> plist;
int n;
void eratosthenes() {
    for (int i = 2; i <= n; i++) is_prime[i] = true;
    for (int i = 2; i * i <= n; i++) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    eratosthenes();
    for (int i = 2; i <= n; i++) if (is_prime[i]) plist.push_back(i);
    int s = 0, e = 0, res = 0, sum = 0;
    int psize = plist.size();
    while (true) {
        if (sum == n) res++;
        if (sum >= n) sum -= plist[s++];
        else if (e == psize) break;
        else sum += plist[e++];
    }
    cout << res;
 
    return 0;
}
 cs

 

반응형
저작자표시

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

[백준 1484번] 다이어트  (0) 2020.03.07
[백준 1806번] 부분합  (0) 2020.03.05
[백준 2003번] 수들의 합 2  (0) 2020.03.05
[백준 2904번] 수학은 너무 쉬워  (0) 2020.03.04
[백준 11690번] LCM(1, 2, ..., n)  (0) 2020.03.02
반응형

문제 링크: 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

<문제 풀이>

투 포인터 알고리즘

<C++ 소스코드>

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
#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
int a[10000];
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    int res = 0, sum = 0, s = 0, e = 0;
 
    while (true) {
        if (sum == m) res++;
        if (sum >= m) sum -= a[s++];
        else if (e == n) break;
        else sum += a[e++];
    }
    cout << res;
 
 
 
    return 0;
}
 cs

 

반응형
저작자표시

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

[백준 1806번] 부분합  (0) 2020.03.05
[백준 1644번] 소수의 연속합  (0) 2020.03.05
[백준 2904번] 수학은 너무 쉬워  (0) 2020.03.04
[백준 11690번] LCM(1, 2, ..., n)  (0) 2020.03.02
[백준 12727번] Numbers(small)  (0) 2020.03.01
반응형

문제 링크: https://www.acmicpc.net/problem/2904

 

2904번: 수학은 너무 쉬워

문제 상근이의 할머니는 매우 유명한 수학자이다. 할머니는 매일 수학 문제로 상근이를 힘들게 한다. 할머니는 종이 N장에 숫자를 하나씩 쓴 다음 상근이에게 준다. 그 다음 상근이는 다음과 같이 문제를 풀어야 한다. 두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다. 상근이는 위의 행동을 무한히 반복할 수 있다. 할머니는 상근이가 만든 수를 보고 점수를 계산한다. 점수가 높을수

www.acmicpc.net

<문제 풀이>

[산술의 기본 정리] 모든 양의 정수는 소인수 분해를 갖는다.

 

즉 모든 양의 정수는 소수의 곱으로 표현할 수 있습니다.

 

이는 마찬가지로 공약수 또한 소수의 곱으로 표현할 수 있습니다.

 

이러한 성질을 이용하면 결국 문제에서 원하는 모든 수에 적힌 최대공약수의 최댓값을 구하려면 각각의 점수를 소인수 분해했을 때 공통적으로 들어있는 소수의 곱이 최대가 되면 됩니다.

 

[두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다.]

 

위 문제 조건을 잘 생각해보면 어떤 한 점수를 소인수 분해해서 나온 소수들 중 하나를 떼서(나눠서) 다른 점수에 붙일 수(곱해서) 있습니다.

 

결국 모든 점수들의 최대 공약수가 최대가 되도록 조건을 이용해서 구하는 방법은 각각의 점수를 소인수 분해 한 다음 소수들을 골고루 분배하면 됩니다.

 

문제의 테스트 케이스 예제를 예로 들어보겠습니다.

 

N = 3

 

8, 24, 9 각각을 소인수 분해합니다.

 

8 = 2 x 2 x 2

24 = 2 x 2 x 2 x 3
9 = 3 x 3

 

8, 24에 2를 9에 떼어주고 9에 있는 3을 8에 떼어주면 공통된 소수는 2 x 2 x 3 = 12(GCD)가 되고

이때 총 3번 떼어줬으니 3회 시도입니다.

 

최대가 되는 GCD를 구하는 방법은 잘 생각해보면 N개의 수를 소인수 분해해서 나오는 각각의 소수 개수를 N으로 나누면 됩니다. (분배 효과)
2  : 6개 -> 3으로 나누면 -> 2개 -> 2 x 2
3 : 2개 -> 3으로 나누면 -> 1개 -> 3
따라서 GCD = 2 x 2 x 3

 

그리고 총 이동 횟수를 구하는 방법은

 

if(각각의 점수에서 각각의 소수의 등장 횟수) < (분배되야할 각 소수의 개수) 
    총 이동 횟수 +=  (분배되야할 각 소수의 개수) -  (각각의 점수에서 각각의 소수의 등장 횟수)

 

배열은 전체에서 각 소수들이 몇 개가 사용됐는지 체크하는 1차원 배열 과 각 점수에서 몇 개의 소수가 사용됐는지 체크하는 2차원 배열 두 개가 필요합니다.

 

<C++ 소스 코드>

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
#include <iostream>
#include <vector>
using namespace std;
 
#define MAX 1000000
bool isPrime[MAX + 1];
int visited[MAX + 1];
 
 
void SieveOfEratosthenes() {
    for (int i = 2; i <= MAX; i++) {
        isPrime[i] = true; // 처음에 모두 소수라고 가정
    }
    for (int i = 2; i * i <= MAX; i++) { //2 부터 sqrt(n) 까지
        if (!isPrime[i]) continue; //이미 지워진 수는 무시
        for (int j = i * i; j <= MAX; j += i) { // 자기자신을 제외한 배수를 모두
            isPrime[j] = false; // 지운다
        }
    }
}
 
int power(int x, int y) {
    int res = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            res = res * x;
        }
        y /= 2;
        x = x * x;
    }
    return res;
}
 
int main(void) {
    SieveOfEratosthenes();
    int n;
    cin >> n;
    vector<int> plist;
    for (int i = 1; i <= MAX; i++) if (isPrime[i]) plist.push_back(i);
    vector<vector<int> > v(n, vector<int>(plist.size(), 0));
 
    for (int i = 0; i < n; i++) {
        int score;
        cin >> score;
        for (int j = 0; j < plist.size(); j++) {
            if (score == 1) break;
            while (score % plist[j] == 0) {
                score /= plist[j];
                visited[plist[j]]++; //전체 들어있는 소수의 개수
                v[i][j]++; // i번째 숫자에 사용되는 각 소수의 개수
            }
        }
    }
    int gcd = 1;
    int cnt = 0;
    for (int i = 0; i < plist.size(); i++) {
        int d = visited[plist[i]] / n; //최소로 분배되야할 각 소수의 개수
        for (int j = 0; j < n; j++) {
            if (v[j][i] < d) { 
                cnt += d - v[j][i]; // 분배
            }
        }
        gcd *= power(plist[i], d);
    }
    cout << gcd << " "<<cnt;
 
    return 0;
}
 cs

 

 

반응형
저작자표시

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

[백준 1644번] 소수의 연속합  (0) 2020.03.05
[백준 2003번] 수들의 합 2  (0) 2020.03.05
[백준 11690번] LCM(1, 2, ..., n)  (0) 2020.03.02
[백준 12727번] Numbers(small)  (0) 2020.03.01
[백준 12925번] Numbers  (0) 2020.03.01
반응형

 

문제 링크: https://www.acmicpc.net/problem/11690

 

11690번: LCM(1, 2, ..., n)

첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다.

www.acmicpc.net

<문제 풀이>

n 이하의 소수들에 대해서 각 소수들의 n 이하의 거듭제곱의 최댓값을 구해서 모두 곱하면 됩니다.

 

<시간 초과 주의할 점>

에라토스테네스의 체를 사용할 때 sqrt(n) 사용

 

배열의 true값를 이용해서 소수를 사용할 때 짝수번째 인덱스는 확인하지 말고 홀수번째만 확인

 

<C++ 소스 코드>

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
 
ll mod = (ll)1 << 32;
bool is_prime[100000001];
vector<int> plist;
 
void sieve(int n) {
    for (int i = 2; i <= n; i++) is_prime[i] = true;
    for (int i = 2; i * i <= n; i++) {
        if (!is_prime[i]) continue;
        for (int j = i*i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    sieve(n);
    ll res = 1;
    plist.push_back(2);
    for (int i = 3; i <= n; i+=2) {
        if (is_prime[i])plist.push_back(i);
    }
    for (auto& prime : plist) {
        ll power = prime;
        while (power * prime <= n) {
            power *= prime;
        }
        res = (res * power) % mod;
    }
    cout << res;
    return 0;
}
 
 cs

 

 

반응형
저작자표시

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

[백준 2003번] 수들의 합 2  (0) 2020.03.05
[백준 2904번] 수학은 너무 쉬워  (0) 2020.03.04
[백준 12727번] Numbers(small)  (0) 2020.03.01
[백준 12925번] Numbers  (0) 2020.03.01
[백준 12728번] n제곱 계산  (0) 2020.03.01
반응형

문제 링크: https://www.acmicpc.net/problem/12727

 

12727번: Numbers (Small)

The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n. Limits 1 <= T <= 100 2 <= n <= 30

www.acmicpc.net

<문제 풀이> 수학

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

 

12728번: n제곱 계산

이 문제에서 숫자 (3 + √5)n 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다. 예를 들어, n = 5 일 때 (3 + √5)5  = 3935.73982 ... 이므로 답은 935입니다. n = 2 인 경우 (3 + √5)2 = 27.4164079 … 이므로, 답은 027입니다.

www.acmicpc.net

백준 12728번의 n제한이 작은 버전

12728번 풀이를 참조해서 점화식을 구하면 됨 

이 문제는 점화식 dp로 O(n)에 해결 가능하다.

반응형
저작자표시

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

[백준 2904번] 수학은 너무 쉬워  (0) 2020.03.04
[백준 11690번] LCM(1, 2, ..., n)  (0) 2020.03.02
[백준 12925번] Numbers  (0) 2020.03.01
[백준 12728번] n제곱 계산  (0) 2020.03.01
[백준 11444번] 피보나치 수 6  (0) 2020.02.29
반응형

문제 링크: https://www.acmicpc.net/problem/12925

 

12925번: Numbers

각 Test case에 대해, “Case #c: x”의 형식으로 각 줄에 정답을 출력한다. c는 Test Case의 번호이다. (1부터 매겨진다.) x는 해당 Test Case의 정답이다.

www.acmicpc.net

<문제 풀이> 수학, 선형대수학, 행렬 거듭제곱

https://seokjin2.tistory.com/13

 

[백준 12728번] n제곱 계산

문제 링크: https://www.acmicpc.net/problem/12728 12728번: n제곱 계산 이 문제에서 숫자 (3 + √5)n 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다. 예를 들어, n = 5 일 때 (3 + √5)5 = 3935..

seokjin2.tistory.com

[백준 12728번]랑 똑같은 문제

 

<C++ 소스코드>

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
typedef long long ll;
typedef vector<vector<ll> > matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 1000;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test_case;
    cin >> test_case;
    for(int i=1; i<= test_case; i++){
        ll n;
        cin >> n;
        matrix a = { {6,-4}, {1, 0} };
        matrix res = power(a, n - 1);
        string ans = to_string((((28 * res[1][0] + 6 * res[1][1]) - 1) % 1000 + 1000) % 1000);
        ll size = ans.size();
        while (true) {
            if (size == 3) break;
            ans = "0" + ans;
            size++;
            
        }
        cout << "Case #" << i << ": " << ans << '\n';
     }
    
 
    return 0;
}
 
 cs
반응형
저작자표시

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

[백준 11690번] LCM(1, 2, ..., n)  (0) 2020.03.02
[백준 12727번] Numbers(small)  (0) 2020.03.01
[백준 12728번] n제곱 계산  (0) 2020.03.01
[백준 11444번] 피보나치 수 6  (0) 2020.02.29
[백준 2749번] 피보나치 수 3  (0) 2020.02.29
반응형

문제 링크: https://www.acmicpc.net/problem/12728

 

12728번: n제곱 계산

이 문제에서 숫자 (3 + √5)n 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다. 예를 들어, n = 5 일 때 (3 + √5)5  = 3935.73982 ... 이므로 답은 935입니다. n = 2 인 경우 (3 + √5)2 = 27.4164079 … 이므로, 답은 027입니다.

www.acmicpc.net

 

<문제 풀이> 수학, 선형대수학, 행렬 거듭제곱

 

[구한 정수부분을 1000으로 나눈 나머지가 뒤에 세자리인데 음수도 나올 수 있으므로 C++로 구현할 때 음수 모듈러 처리를 해줘야됩니다.]

 

<C++ 소스코드>

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
typedef long long ll;
typedef vector<vector<ll> > matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 1000;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test_case;
    cin >> test_case;
    for(int i=1; i<= test_case; i++){
        ll n;
        cin >> n;
        matrix a = { {6,-4}, {1, 0} };
        matrix res = power(a, n - 1);
        string ans = to_string((((28 * res[1][0] + 6 * res[1][1]) - 1) % 1000 + 1000) % 1000);
        ll size = ans.size();
        while (true) {
            if (size == 3) break;
            ans = "0" + ans;
            size++;
            
        }
        cout << "Case #" << i << ": " << ans << '\n';
     }
    
 
    return 0;
}
 
 cs

 

반응형
저작자표시

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

[백준 12727번] Numbers(small)  (0) 2020.03.01
[백준 12925번] Numbers  (0) 2020.03.01
[백준 11444번] 피보나치 수 6  (0) 2020.02.29
[백준 2749번] 피보나치 수 3  (0) 2020.02.29
[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)  (2) 2020.02.28
반응형

문제 링크: https://www.acmicpc.net/problem/11444

 

11444번: 피보나치 수 6

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

<문제 풀이> 수학, 선형대수학, 행렬 거듭제곱

백준 2749번 피보나치 수 3 문제랑 풀이가 똑같습니다. (점화식 -> 행렬 거듭제곱)

https://seokjin2.tistory.com/11

 

[백준 2749번] 피보나치 수 3

문제 링크: https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net <문제 풀이> 수학, 선형대수학,..

seokjin2.tistory.com

<C++ 소스코드>

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
#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef vector<vector<ll> > matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 1000000007;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin >> n;
    matrix a = { {1, 1}, {1, 0} };
    matrix res = (power(a, n - 1));
    cout << (res[1][0] + res[1][1]) % 1000000007;
    
 
    return 0;
}
 cs

 

 

반응형
저작자표시

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

[백준 12925번] Numbers  (0) 2020.03.01
[백준 12728번] n제곱 계산  (0) 2020.03.01
[백준 2749번] 피보나치 수 3  (0) 2020.02.29
[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)  (2) 2020.02.28
[백준 10854번] Divisions  (0) 2020.02.25

+ Recent posts

티스토리툴바