백준 BOJ 기하, 에라토스테네스의 체, DP 등등.. 220802

백준 BOJ 16488번: 피카츄가 낸 어려운 문제

문제 난이도 : Silver V

알고리즘 분류 : 기하학

 

AB = AC인 이등변삼각형 ABC에 대해 BC에 K개의 점 P_i를 잡고 함수 F(i)를 (선분 AP_i의 길이)^2 + (선분 BP_i의 길이) × (선분 CP_i의 길이)로 정의할 때, F(1)+F(2)+···+F(K)의 값을 구하는 문제이다.

 

 

 

 

굳이 증명을 하지 않아도 삼각형을 어떻게 잡아도 조건만 만족하면 같은 답이 나온다는 사실을 유추할 수 있으므로, 가장 구하기 쉬운 상황 하나를 만들어 그려보면 된다.

예를 들어 위와 같이 직각이등변삼각형을 잡고 P를 한 점으로 고정시켜 생각해보면 답은 N^2 K임을 알 수 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int a, b; cin >> a >> b;

    cout << a * a * b << "\n";
}

 

 

백준 BOJ 3097번 : 산책 경로

문제 난이도 : Silver IV

알고리즘 분류 : 기하학, 브루트포스

 

N개의 벡터가 주어질 때, 벡터의 합을 구하고, 또한 N개의 벡터 중 하나를 제거한 합이 가장 짧은 벡터의 길이를 구하는 문제이다.

 

각 벡터의 합은 간단히 구해줄 수 있고, 하나를 제거한 가장 짧은 벡터 또한 2중 for문을 돌리면서 한 개씩 뺀 경우를 따져보면 된다. 단순 브루트포스 문제이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int x, y; };

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<s> v(N);

    int x = 0, y = 0;

    for(int i=0; i<N; i++) {
        cin >> v[i].x >> v[i].y;

        x += v[i].x;
        y += v[i].y;
    }

    cout << x << " " << y << "\n";

    double Min = INT_MAX;

    for(int i=0; i<N; i++) {
        x = 0, y = 0;

        for(int j=0; j<N; j++) {
            if(j == i) continue;

            x += v[j].x;
            y += v[j].y;
        }

        Min = min(Min, sqrt(x*x + y*y));
    }

    cout << fixed;
    cout.precision(2);

    cout << Min << "\n";
}

 

 

백준 BOJ 19250번 : Flat Earth

문제 난이도 : Silver V

알고리즘 분류 : 기하학

 

중심 좌표가 (x, y, z)이고 반지름이 r인 구를 ax + by + cz + d = 0인 평면에 정사영했을 때 나타나는 도형의 넓이를 구하는 문제이다.

 

구를 평면에 정사영시키면 반지름이 같은 원이 생긴다.

따라서 다른 변수는 고려할 필요없이 pi * r^2을 답으로 얻어주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cout << fixed;
    cout.precision(6);

    int T; cin >> T;

    while(T--) {
        int v[8];
        for(int i=0; i<8; i++) cin >> v[i];

        cout << M_PI * v[3] * v[3] << "\n";
    }
}

 

 

백준 BOJ 17286번 : 유미

문제 난이도 : Silver V

알고리즘 분류 : 기하학

 

유미의 위치가 주어지고, 3개의 점이 주어질 때 유미의 위치에서 3개의 점을 거치는 최단 경로의 길이를 구하는 문제이다.

 

3개 점의 위치를 방문하는 순서는 총 8가지가 존재하므로, 이 8가지를 모두 구해보면 된다.

코드를 짧게 작성하려면 정렬과 next_permutation을 다음과 같이 활용하면 비교적 간편하게 구현할 수 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<pair<double, double>> v(4);

    for(int i=0; i<4; i++) cin >> v[i].first >> v[i].second;

    sort(v.begin()+1, v.end());

    double Min = INT_MAX;

    while(true) {
        double sum = 0;

        for(int i=1; i<4; i++)
            sum += sqrt(pow(v[i].first - v[i-1].first, 2) + pow(v[i].second - v[i-1].second, 2));

        Min = min(Min, sum);

        if(!next_permutation(v.begin()+1, v.end())) break;
    }

    cout << (int)Min << "\n";
}

 

 

백준 BOJ 9421번 : 소수상근수

문제 난이도 : Gold V

알고리즘 분류 : 에라토스테네스의 체

 

각 자리수의 제곱의 합을 만들어 새로운 수를 만들고, 이 과정을 반복하다가 1이 얻어지는 수를 상근수라고 할 때, 주어진 N에 대해 N 이하인 소수인 상근수들을 모두 구하는 문제이다.

 

N이 100만 이하이지만 소수인 수들을 먼저 걸러내고 그 수들 중에서만 탐색하면 시간이 별로 걸리지 않는다.

따라서 에라토스테네스의 체로 소수들을 미리 구하고 각 자릿수의 제곱의 합을 구하는 과정을 반복하면서 답을 구해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e6 + 1;

    vector<bool> p(Max, true);
    p[1] = true;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int N; cin >> N;

    for(int i=0; i<v.size() && v[i] <= N; i++) {
        map<int, bool> m;
        m[v[i]] = true;

        int cur = v[i];
        bool check = true;

        while(true) {
            int sum = 0;

            while(cur > 0) {
                sum += (cur % 10) * (cur % 10);
                cur /= 10;
            }

            cur = sum;

            if(cur == 1) {
                cout << v[i] << "\n";
                break;
            }

            if(m[cur]) break;
            m[cur] = true;
        }
    }
}

 

 

백준 BOJ 23048번 : 자연수 색칠하기

문제 난이도 : Gold V

알고리즘 분류 : 에라토스테네스의 체

 

N 이하의 자연수들을 색칠할 때, 서로소 관계인 두 수는 다른 색으로 칠하려면 최소 몇 가지의 색이 필요하고 또한 그 때의 예시를 하나 구하는 문제이다.

 

소수는 다른 소수와 무조건 서로소 관계이므로  1부터 시작하여 작은 소수부터 배수인 것들을 같은 색으로 칠해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 5e5 + 1;

    vector<bool> p(Max, true);
    p[1] = true;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int N; cin >> N;

    int cnt = 0;

    vector<int> u(N+1);

    for(int i=1; i<=N; i++) {
        if(!p[i]) continue;

        cnt++;

        for(int j=i; j<=N; j+=i) u[j] = cnt;
    }

    cout << cnt << "\n";

    for(int i=1; i<=N; i++) cout << u[i] << " ";
    cout << "\n";
}

 

 

백준 BOJ 15540번 : Calling Extraterrestrial Intelligence Again

문제 난이도 : Gold V

알고리즘 분류 : 에라토스테네스의 체

 

N, a, b에 대해 a/b <= p/q <= 1이고 pq <= N인 pq가 최댓값을 가지는 소수 p, q를 구하는 문제이다.

 

잘 보면 문제에서 조건식을 다 줘서 그대로 수식으로 옮기기만 하면 된다.

대신 시간 초과를 피하기 위해 에라토스테네스의 체로 소수들을 미리 구해놓고, 소수들에 대해서만 조건식을 만족하는 값들의 최댓값을 조사하면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e5 + 1;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    while(true) {
        int N, a, b; cin >> N >> a >> b;
        if(N == 0 && a == 0 && b == 0) break;

        int Max = 0, p, q;

        for(int i=0; i<v.size() && v[i] <= N; i++)
            for(int j=i; j<v.size() && v[i]*v[j] <= N; j++)
                if(v[i]*b >= v[j]*a && v[i]*v[j] > Max) {
                    p = v[i], q = v[j];
                    Max = p * q;
                }

        cout << p << " " << q << "\n";
    }
}

 

 

백준 BOJ 19699번 : 소-난다!

문제 난이도 : Silver I

알고리즘 분류 : 백트래킹, 소수 판정

 

N개의 소 중 M마리 소의 몸무게를 합쳐 소수를 만들 때, 가능한 몸무게의 합들을 구하는 문제이다.

 

N이 9 이하이므로 백트래킹으로 가능한 모든 조합을 검사해볼 수 있다.

이 때 각 소의 무게는 최대 1,000이므로, 대략 9,000 이하의 모든 소수들을 미리 찾아놓아야 시간 초과가 걸리지 않는다.

따라서 소수들을 미리 구해놓고 백트래킹으로 가능한 조합들을 모두 찾아주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<bool> p;
vector<int> v, u, w;
int N, M;

void f(int idx, int cnt, int sum) {
    if(idx == N) {
        if(cnt == M && p[sum]) w.push_back(sum);
        return;
    }

    f(idx + 1, cnt, sum);
    f(idx + 1, cnt + 1, sum + u[idx]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e4 + 1;

    p.resize(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    cin >> N >> M;

    u.resize(N);
    for(int i=0; i<N; i++) cin >> u[i];

    f(0, 0, 0);

    if(w.size() == 0) {
        cout << -1 << "\n";
        return 0;
    }

    sort(w.begin(), w.end());
    w.erase(unique(w.begin(), w.end()), w.end());

    for(int i=0; i<w.size(); i++) cout << w[i] << " ";
    cout << "\n";
}

 

 

백준 BOJ 24758번 : RSA Mistake

문제 난이도 : Gold V

알고리즘 분류 : 에라토스테네스의 체

 

입력된 두 수에 대해 두 수가 서로 다른 소수이면 full credit, full credit은 아니지만 두 수를 곱한 수가 2 이상의 k에 대한 k^2를 약수로 가지지 않는 경우 partial credit, 그 외는 no credit을 출력하는 문제이다.

 

소수들을 미리 벡터에 구해놓고 v[i] * v[i] <= N인 v[i]들에 대해 검사를 하며 소인수 분해를 해서 두 수의 소인수들을 한 벡터에 저장한다.

그 다음 중복되는 원소가 있는지를 검사하여 partial credit의 여부를 파악할 수 있다.

full credit은 소인수 분해로 단 한 번도 분해가 되지 않았으면 해당된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e6 + 1;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int a, b; cin >> a >> b;

    bool b1 = true, b2 = true;
    map<int, int> m;
    vector<int> u;

    int tmp = a;
    for(int i=0; i<v.size() && v[i]*v[i] <= a; i++)
        if(a % v[i] == 0) {
            b1 = false;

            while(tmp % v[i] == 0) {
                m[v[i]]++;
                tmp /= v[i];
                u.push_back(v[i]);
            }
        }
    if(tmp > 1) u.push_back(tmp);

    tmp = b;
    for(int i=0; i<v.size() && v[i]*v[i] <= b; i++)
        if(b % v[i] == 0) {
            b2 = false;

            while(tmp % v[i] == 0) {
                m[v[i]]++;
                tmp /= v[i];
                u.push_back(v[i]);
            }
        }
    if(tmp > 1) u.push_back(tmp);

    int x = u.size();

    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());

    int y = u.size();

    if(x == y && b1 && b2) cout << "full credit\n";
    else if(x == y) cout << "partial credit\n";
    else cout << "no credit\n";
}

 

 

백준 BOJ 16400번 : 소수 화폐

문제 난이도 : Gold V

알고리즘 분류 : 에라토스테네스의 체, DP

 

N을 소수만의 합으로 나타내는 경우의 수를 구하는 문제이다.

 

에라토스테네스의 체로 미리 소수들을 구해놓고, 배낭 문제의 dp 점화식을 활용하면 쉽게 해결이 가능한 문제이다.

옆의 '프로그래밍/알고리즘 구현 코드 모음' 카테고리의 N원으로 M원을 만드는 경우의 수 구하기 부분에 있는 코드와 완전히 동일한 점화식이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 4e4 + 1;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int N; cin >> N;

    vector<int> dp(N+1);
    dp[0] = 1;

    for(int i=0; i<v.size(); i++)
        for(int j=v[i]; j<=N; j++) dp[j] = (dp[j] + dp[j - v[i]]) % 123456789;

    cout << dp[N] << "\n";
}

 

 

백준 BOJ 4172번 : sqrt log sin

문제 난이도 : Silver II

알고리즘 분류 : DP

 

주어진 점화식에 대해, i번째 수를 구하는 쿼리 여러 개를 수행하는 문제이다.

 

i의 최댓값이 100만이고, 쿼리가 여러 번 들어올 수 있으므로 dp로 미리 값을 구해두면 된다.

점화식이 이미 있으므로 수식을 그대로 옮기는 과정만 거치면 된다.

int형과 double형의 혼용을 주의하자.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<int> dp(1e6 + 1);
    dp[0] = 1;

    for(int i=1; i<=1e6; i++) {
        double x = i;

        dp[i] = (dp[(int)(x - sqrt(x))] + dp[(int)(log(x))] + dp[(int)(x * sin(x) * sin(x))]) % (int)(1e6);
    }

    while(true) {
        int N; cin >> N;
        if(N == -1) break;

        cout << dp[N] << "\n";
    }
}

 

 

백준 BOJ 6193번 : Hungry Cows

문제 난이도 : Silver II

알고리즘 분류 : DP, LIS

 

소들의 번호 N개가 주어졌을 때 증가하는 순으로 가장 많이 뽑았을 때의 소의 수를 구하는 문제이다.

 

이 문제는 가장 긴 증가하는 부분 수열, LIS라는 유명한 문제이므로 별도로 설명은 없다. (다른 포스트에 작성되어 있으니, 원리가 궁금하다면 검색을 권한다.)

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    vector<int> u;
    u.push_back(v[0]);

    int cnt = 0;

    vector<pair<int, int>> dp(N);
    dp[0] = {v[0], 0};

    for(int i=1; i<N; i++) {
        if(v[i] > u.back()) {
            u.push_back(v[i]);
            cnt++;

            dp[i] = {v[i], cnt};
        }
        else {
            int x = lower_bound(u.begin(), u.end(), v[i]) - u.begin();
            u[x] = v[i];

            dp[i] = {v[i], x};
        }
    }

    cout << cnt + 1 << "\n";
}

 

 

백준 BOJ 4620번 : Pascal's Travels

문제 난이도 : Silver II

알고리즘 분류 : DP

 

(1, 1)에서 시작하여 현재 칸에 써 있는 숫자만큼 오른쪽 또는 아래로 이동이 가능할 때, 주어진 배열에 대해 (1, 1)에서 (N, N)으로 이동하는 경우의 수를 구하는 문제이다.

 

대표적인 DP 문제로, 처음 서 있는 위치 (1, 1)의 경우의 수를 1가지로 놓고 오른쪽과 아래로 이동할 수 있는 값들을 누적시켜나가면서 반복문을 돌려주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        int N; cin >> N;
        if(N == -1) break;

        vector<vector<int>> v(N, vector<int>(N));

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++) {
                char c; cin >> c;

                v[i][j] = c - '0';
            }

        vector<vector<int>> dp(N, vector<int>(N));
        dp[0][0] = 1;

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++) {
                if(v[i][j] == 0) continue;

                if(i + v[i][j] < N) dp[i + v[i][j]][j] += dp[i][j];
                if(j + v[i][j] < N) dp[i][j + v[i][j]] += dp[i][j];
            }

        cout << dp[N-1][N-1] << "\n";
    }
}

 

 

백준 BOJ 10752번 : Cow Hopscotch

문제 난이도 : Silver II

알고리즘 분류 : DP

 

출발 지점에서 시작하여 오른쪽 아래에 있으면서 문자가 현재 위치와 서로 다른 칸으로 이동하며 맨 오른쪽 맨 아래 칸으로 이동하는 경우의 수를 구하는 문제이다.

 

백준 BOJ 10748번 : Cow Hopscotch 문제와 거의 비슷한 문제이다.

위의 문제에서 숫자가 알파벳으로 바뀌기만 했다고 생각하면 된다.

DP를 이용하여 한 칸을 방문할 때마다 그 기준으로 모든 오른쪽 아래 칸들을 다 검사해주어야 한다.

즉, 4중 반복문이 사용되는데 이 문제에서는 어차피 범위가 아주 작으므로 시간 초과를 걱정할 필요는 없다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<vector<int>> v(N, vector<int>(M));
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) {
            char c; cin >> c;

            if(c == 'R') v[i][j] = 1;
            else if(c == 'B') v[i][j] = 2;
        }

    vector<vector<int>> dp(N, vector<int>(M));
    dp[0][0] = 1;

    for(int i=1; i<N; i++)
        for(int j=1; j<M; j++)
            for(int k=0; k<i; k++)
                for(int l=0; l<j; l++)
                    if(v[k][l] != v[i][j]) dp[i][j] += dp[k][l];

    cout << dp[N-1][M-1] << "\n";
}