문제 : https://www.acmicpc.net/problem/15711

에라토스테네스체 소수 골드바흐의추측 정수론

[ 알고리즘풀이 ]

 

 우리는 A + B가 두 소수의 합으로 표현되는지 판단해야된다. ( A + B 를 S 라고 표현하겠다 )

 1) S 가 짝수인 경우

 --> 골드바흐가 짝수인 수는 '2'를 제외하고 모두 두 소수의 합으로 표현이 가능하다고 추측했고, 10^18 이하의 숫자에 대해서는 해당 추측이 참이라고 증명이 됐다.

 --> '2'를 제외하고 S가 짝수인 경우는 두 소수의 합으로 표현 할 수 있다!

 --> '2' 는 두 소수의 합으로 표현이 불가능하다

 

 2) S 가 홀수인 경우

 --> 홀수는 짝수 + 홀수로만 표현이 가능하다. 즉, 짝수 소수 + 홀수 소수로 표현이 가능한지 아닌지 판단하면 된다.

 --> 짝수 소수는 '2' 밖에 없으므로 우리는 ( S - 2 ) 가 소수인지 아닌지 판단하면 된다.

 --> S가 최대 4 * 10^12 이므로 우리는 route(4 * 10^12) 인 2 * 10^6 이하의 소수만 알고있으면 S가 큰 값이 들어오더라도 소수인지 아닌지 판단이 가능하다.

 --> 따라서 에라토스테네스 체를 이용해 2 * 10^6 이하의 소수들을 다 구해놓고 ( S - 2 ) 가 2 * 10^6 보다 작다면 에라토스테네스 체로 바로 소수인지 판단하고, 2 * 10^6 보다 크다면 에라토스테네스 체로 구해놓은 소수들로 다 나누어보면 된다.

 

[ 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
#include<iostream>
#include<vector>
 
using namespace std;
 
const int MAX_LENGTH = 2000000;
vector<int> prime;
bool eratos[MAX_LENGTH + 1];
 
void eratosthenes(void) { // 에라토스테네스체로 2백만 이하의 모든 소수를 구하자 false면 소수
    eratos[0] = eratos[1] = true;
    for (int i = 2; i <= MAX_LENGTH; i++) {
        if (eratos[i] == false) {
            prime.push_back(i);
            for (int j = i * 2; j <= MAX_LENGTH; j += i)
                eratos[j] = true;
        }
    }
}
 
bool isPrime(long long A) {
    if (A <= MAX_LENGTH) return !eratos[A];
    else{
        for (int i = 0; i < prime.size(); i++)
            if ( A % prime[i] == 0)
                return false;
        return true;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    eratosthenes();
 
    int T;
    cin >> T;
    while (T--) {
        long long A, B, S;
        cin >> A >> B;
        S = A + B;
        if (S == 2) cout << "NO\n";
        else if (S % 2 == 0) cout << "YES\n"; // 골드바흐의추측
        else { // S가 홀수라면 --> 짝수 + 홀수 꼴만 가능 --> 짝수 소수는 2 밖에 없음
            if (isPrime(S - 2)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ15711.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1202 : LOPOV  (0) 2020.08.28
[BOJ] 2636 : 치즈  (0) 2020.08.27
[BOJ] 1826 : 연료 채우기  (1) 2020.08.26
[BOJ] 9881 : Ski Course Design  (0) 2020.08.25
[BOJ] 13711 : LCS 4  (0) 2020.08.25

문제 : https://www.acmicpc.net/problem/1826

그리디 탐색

[ 문제해석 ]

 

 아래와 같은 2가지 이유 때문에 연료를 중심으로 그리디하게 접근해야 된다.

 

 1) 현재 가지고 있는 연료 = 현재 내가 갈 수 있는거리

 내가 현재 나갈 수 있는 거리는 내 거리에서 가지고 있는 연료만큼 이동할 수 있다. 따라서, 연료랑 내가 갈 수 있는 거리는 동일한 의미로 해석할 수 있다!

 

 2) 주유소 연료 + 현재 가지고 있는 연료 = 주유소 들려서 갈 수 있는 거리

 내가 현재 가지고 있는 연료로 갈 수 있는 주유소가 K개 있다고 해보자. 어차피 K개의 주유소는 내가 지금 다 들릴 수 있고 우리는 도착 지점까지 주유소를 적게 들리고 이동해야 한다.

 --> 이왕 주유소에 들릴 거면 들렸을 때 가장 멀리 갈 수 있는 주유소에 들리는 게 좋다!

 --> 주유소에서 얻을 수 있는 연료 + 내가 가지고 있는 연료 = 주유소에 들려서 갈 수 있는 거리이므로 들릴 수 있는 주유소 중에서 연료가 제일 많은 곳이 의미가 있다!

 

예를 들어, 내가 연료가 10인 상태에서 시작하고 (2,4) / (6,5) 에 주유소가 있다고 하자. 
(2, 4) 주유소는 연료를 2만 쓰고 4를 얻을 수 있고, 
(6, 5) 주유소는 연료를 6이나 쓰고 5를 얻을 수 있으므로 (2,4) 가 더 유리해 보인다.
--> 이게 함정!! 
(2, 4) 를 들리면 연료가 12가 남고 (6, 5) 를 들리면 연료가 9 가 남지만  
실제로 (2, 4)를 들리면 나는 최대 14까지 갈 수 있고 (6, 5)를 들리면 나는 최대 15까지 갈 수 있음 
--> 내가 갈 수 있는 주유소 중에서 연료를 제일 많이 주는 주유소들을 계속 탐색해야됨! 

 

[ 알고리즘풀이 ]

 

 L = 도착지점

 curL = 현재 연료양 = 현재 갈 수 있는 거리

 ans = 주유소 들린 횟수

 curP = 현재 연료양으로 갈 수 있는 주유소 인덱스

  

 0) 현재 연료양으로 도착지점에 갈 수 있는지 체크한다. (curL < L)

 1) 도착할 수 없다면, priority_queue 를 이용해서 현재 갈 수 있는 주유소의 연료를 다 push한다.

 2) 우리는 어차피 갈 수 있는 주유소 중에서 연료를 제일 많이 주유소가 필요!

 --> 가장 연료를 많이 주는 주유소를 들리자.
 --> curL += pq.top(); ( 가장 많이 주는 주유소에 들려 연료 충전! )

 --> ans++;  ( 주유소에 방문함 )

 3) 0~2) 과정을 반복한다! 이때, 모든 주유소를 방문해봐서 priority_queue 가 비었는데도 도착지점에 도착할 수 없다면 -1 을 출력한다.

 

[ 코드 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
#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N, L, P;
    pair<int, int> gasStation[10000];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> gasStation[i].first >> gasStation[i].second;
    cin >> L >> P;
 
    sort(gasStation, gasStation + N);
 
    // P연료를 가지고 L까지 가야된다!
    priority_queue<int> pq;
 
    int curP = 0, curL = P, ans = 0;
    while (curL < L) {
        while (curP < N && gasStation[curP].first <= curL) {
            pq.push(gasStation[curP++].second);
        }
        if (pq.empty()) { // L 에 도착도 못했고, 더 이상 갈 곳도 없음.
            ans = -1;
            break;
        }
        curL += pq.top();
        pq.pop();
        ans++;
    }
    cout << ans << '\n';
    return 0;
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1826.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 2636 : 치즈  (0) 2020.08.27
[BOJ] 15711 : 환상의 짝궁  (0) 2020.08.27
[BOJ] 9881 : Ski Course Design  (0) 2020.08.25
[BOJ] 13711 : LCS 4  (0) 2020.08.25
[BOJ] 2632 : 피자판매  (0) 2020.08.24

문제 : https://www.acmicpc.net/problem/9881

[ 문제해석 ]

 N개의 언덕을 가지고 있는데 가장 높은 언덕와 가장 낮은 언덕의 차이를 17 이내로 만들어야된다. 언덕을 k 만큼 쌓거나 깎는데 k * k 만큼의 cost가 발생한다. 이때, 필요한 가장 적은 cost는 얼마인가

 

[ 알고리즘풀이 ]

 N 은 최대 1000, 언덕의 높이도 0 ~ 100 으로 범위가 작다. 즉, 모든 경우에 대해서 cost를 구해봐도 시간 초과에 걸리지 않는다.

 --> 0 ~ 17 / 1 ~ 18 / 2 ~ 19 / .... / 83 ~ 100 과 같이 크기가 17인 모든 범위를 나눈 후, 각 범위마다 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
#include<iostream>
#include<algorithm>
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N, hills[1000];
 
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> hills[i];
 
    int ans = 99999999;
    for (int i = 0; i <= 100 - 17; i++) {
        // i ~ i + 17 까지가 우리가 잡은 범위!
        int tempAns = 0;
        for (int j = 0; j < N; j++) {
            if (hills[j] < i) tempAns += (i - hills[j]) * (i - hills[j]);
            if (hills[j] > i + 17) tempAns += (hills[j] - i - 17) * (hills[j] - i - 17);
        }
        ans = min(ans, tempAns);
    }
    cout << ans << '\n';
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ9881.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 15711 : 환상의 짝궁  (0) 2020.08.27
[BOJ] 1826 : 연료 채우기  (1) 2020.08.26
[BOJ] 13711 : LCS 4  (0) 2020.08.25
[BOJ] 2632 : 피자판매  (0) 2020.08.24
[BOJ] 11964 : Fruit Feast  (0) 2020.08.23

문제 : https://www.acmicpc.net/problem/13711

DP 동적프로그래밍

[ 알고리즘풀이 ]

 입력으로 주어지는 배열 B의 Index를 A 배열을 기준으로 정렬하면 LIS 문제로 바뀌게 된다.

  Sorted배열 [ 3 0 4 1 2 5 ] 에서 가장 긴 LIS는 [ 0 1 2 5 ] 가 되고 이는 다시 생각해보면 B배열의 0, 1, 2, 5 인덱스이므로 실제 B배열에서 [ 1 4 5 6 ] 을 의미한다.

( O(NlogN) 으로 LIS구하기 :  https://travelbeeee.tistory.com/455?category=800452) 

 

[ 코드 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int LIS(vector<int> v) {
    const int INF = 99999999;
    int N = v.size();
    vector<int> Dp(N + 1, INF);
    int longest = 1;
    Dp[0] = -INF;
    Dp[1] = v[0];
    for (int cur : v) {
        if (Dp[longest] < cur) {
            longest++;
            Dp[longest] = cur;
        }
        else {
            vector<int>::iterator it = lower_bound(Dp.begin(), Dp.end(), cur);
            *it = cur;
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++)
        if (Dp[i] != INF) ans = i;
    return ans;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N;
    cin >> N;
    
    vector<int> A(N);
    vector<int> temp(N);
    vector<int> index(N);
 
    for (int i = 0; i < N; i++)
        cin >> A[i];
 
    for (int i = 0, x; i < N; i++) {
        cin >> x;
        temp[x - 1] = i;
    }
 
    for (int i = 0; i < N; i++)
        index[i] = temp[A[i] - 1];
 
    cout << LIS(index);
    
}
 cs

[ github]

https://github.com/travelbeeee/BOJ/blob/master/BOJ13711.cpp

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1826 : 연료 채우기  (1) 2020.08.26
[BOJ] 9881 : Ski Course Design  (0) 2020.08.25
[BOJ] 2632 : 피자판매  (0) 2020.08.24
[BOJ] 11964 : Fruit Feast  (0) 2020.08.23
[BOJ] 18808 : 스티커 붙이기  (0) 2020.08.23

+ Recent posts

티스토리툴바