백준 BOJ 문제 풀이 모음 220804

백준 BOJ 11690번 : LCM (1, 2, ..., n)

문제 난이도 : Gold III

알고리즘 분류 : (빠른) 에라토스테네스의 체

 

1부터 N까지의 자연수들의 최소공배수를 구하는 문제이다.

 

핵심 아이디어는 N 이하의 자연수 중 특정 소인수의 거듭제곱을 가장 많이 포함하고 있는 수가 LCM의 약수가 된다.

예를 들어 N = 10이면 LCM은 2의 거듭제곱을 약수로 가질텐데, 10 이하의 자연수 중 8이 2^3으로 2를 가장 많이 가지고 있으므로, LCM(1, ..., 10)은 2^3을 약수로 가져야 한다.

그러면 이제 10^8 이하의 소수를 구하면 되는데, 먼저 메모리의 경우 bool 벡터로 메모리를 할당할 경우 10^8칸까지는 256MB에 충분히 들어간다.

 

그 다음 코드의 작동 시간을 줄여야 하는데, 수들 중에서 2의 배수인 것이 절반이나 차지하므로 시간을 줄이기 위해 2의 배수는 고려하지 않고 홀수 중에서만 에라토스테네스의 체를 사용하자.

정리하여 다음과 같이 코드를 작성하면 충분히 1000ms 안에 돌아갈 수 있다.

 

 

#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 = 1e8 + 1;
    vector<bool> p(Max);

    vector<int> v;
    v.push_back(2);

    for(int i=3; i<Max; i+=2) {
        if(p[i]) continue;

        v.push_back(i);

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

    int N; cin >> N;

    int ans = 1, mod = 4294967296;

    for(int i=0; i<v.size() && v[i] <= N; i++) {
        int x = 1;

        while(x * v[i] <= N) x *= v[i];

        ans = (ans * x) % mod;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 2482번 : 색상환

문제 난이도 : Gold IV

알고리즘 분류 : DP

 

N개의 원형 색상환에서 M개의 서로 인접하지 않는 색들을 선택하는 경우의 수를 구하는 문제이다.

 

처음부터 원형에서의 경우의 수를 생각하지 말고 일단 직선 상의 N개 중에서 서로 인접하지 않는 M개를 고르는 경우를 먼저 구하고, 그 다음 이것을 가지고 원형에서의 경우의 수를 생각해보면 쉽다.

 

즉, dp[i][j]를 일렬로 놓인 i개의 색 중에서 서로 인접하지 않는 j개의 색을 고르는 경우의 수라고 하자.

그러면 dp[i][j]는, i번째 색을 고르는 경우는 이전 칸이 색칠되면 안 되고 지금 색을 하나 선택할 것이므로 dp[i-2][j-1]과 같고, i번째 색을 고르지 않는 경우는 이전 칸의 색칠 여부는 상관 없고 색 역시 사용 안하므로 dp[i-1][j]가 된다. (dp[i][j] = dp[i-2][j-1])

 

이제 dp[N][N]까지 모두 구했으면, 이제 원형에서 N가지 색 중 서로 인접하지 않는 M개의 색을 고르는 경우를 생각해보자.

N번째 칸을 색칠하는 경우는, N번째 칸을 포함하여 1번째 칸과 N-1번째 칸이 색칠되면 안된다.

그러므로 3개의 칸이 비어있어야 하고 지금 색을 하나 고를 것이므로 색이 하나 덜 골라져 있어야 한다.

이것은 dp[N-3][M-1]과 일대일 대응이 된다.

N번째 칸을 색칠하지 않는 경우는, 그냥 dp[N-1][M]이다.

따라서 답은 dp[N-1][M] + dp[N-3][M-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 N, M; cin >> N >> M;

    vector<vector<int>> dp(N+1, vector<int>(N+1));

    int mod = (int)(1e9 + 3);

    for(int i=0; i<=N; i++) dp[i][0] = 1;
    dp[1][1] = 1;

    for(int i=2; i<=N; i++)
        for(int j=1; j<=N; j++)
            dp[i][j] = (dp[i-1][j] + dp[i-2][j-1]) % mod;

    int ans = (dp[N-1][M] + dp[N-3][M-1]) % mod;

    cout << ans << "\n";
}

 

 

백준 BOJ 12851번 : 숨바꼭질 2

문제 난이도 : Gold IV

알고리즘 분류 : BFS

 

0 ~ 100,000의 좌표가 있을 때 N의 위치에서 시작하여 +1, -1, x2 중 하나를 선택하여 좌표 이동이 가능하다고 할 때, 좌표 M에 도달하기 위한 최소 이동 횟수와 그 이동 횟수로 이동 가능한 방법의 수를 구하는 문제이다.

 

먼저 최소 이동 횟수는 보편적인 BFS로 구현이 가능하다.

문제가 되는 부분은 해당 횟수로 도달 가능한 경우의 수를 구하는 것인데, 한번 vis 체크가 되면 그 칸은 다시 이동할 수 없게 되기 때문에 아이디어가 필요하다.

핵심은 queue에 push하면서 vis를 체크하는 것이 아닌 pop을 하면서 vis를 체크해주는 것인데, 이러면 같은 횟수로 방문하는 경우의 수를 모두 파악할 수 있다.

왜냐하면 queue에는 같은 거리인 노드들이 묶여서 들어가 있어서 최단 횟수로 어떤 노드에 방문했을 경우 같은 횟수로 그 노드에 방문되는 경로가 있더라도 이미 큐에 들어있게 되기 때문이다.

 

 

#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<bool> vis(1e5 + 1);

    queue<pair<int, int>> q;
    q.push({N, 0});

    int dis, cnt = 0;

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        vis[x] = true;

        if(x == M) {
            if(cnt == 0) {
                dis = y;
                cnt++;
            }
            else if(y == dis) cnt++;
        }

        if(x-1 >= 0 && !vis[x-1]) q.push({x-1, y+1});
        if(x+1 <= 1e5 && !vis[x+1]) q.push({x+1, y+1});
        if(x*2 <= 1e5 && !vis[x*2]) q.push({x*2, y+1});
    }

    cout << dis << "\n" << cnt << "\n";
}

 

 

백준 BOJ 1254번 : 팰린드롬 만들기

문제 난이도 : Silver II

알고리즘 분류 : 문자열

 

문자열이 주어질 때, 뒤에 문자를 더 붙여 만들 수 있는 가장 짧은 팰린드롬 문자열의 길이를 구하는 문제이다.

 

두 가지의 경우가 존재하는데, 어떤 문자를 기준으로 양 옆으로 대칭인 길이가 홀수인 팰린드롬을 만들 수 있거나, 어떤 문자와 그 왼쪽 문자를 기준으로 대칭인 길이가 짝수인 팰린드롬을 만들 수 있다.

문제에서 문자열의 길이가 최대 50이라고 하였으므로, 이 두 가지를 브루트포스로 일일이 탐색하여 구할 수 있다.

중심 문자는 반드시 문자열의 가운데에서 오른쪽 부분으로 잡아야 하는데, 왼쪽으로 잡을 경우 문자열의 앞에 문자를 붙여야 팰린드롬이 되는데 이 문제에서는 문자열의 뒤에만 문자를 붙일 수 있기 때문이다.

 

 

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

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

    string str; cin >> str;

    int ans = INT_MAX;

    for(int i=str.length()/2; i<str.length(); i++) {
        bool check = true;

        for(int j=0; i-j>=0 && i+j<str.length(); j++)
            if(str[i-j] != str[i+j]) check = false;

        if(check) ans = min(ans, i*2 + 1);
    }

    for(int i=(str.length()+1)/2; i<str.length(); i++) {
        bool check = true;

        for(int j=0; i-j-1>=0 && i+j<str.length(); j++)
            if(str[i+j] != str[i-1-j]) check = false;

        if(check) ans = min(ans, i*2);
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 12021번 : 보물 찾기

문제 난이도 : Silver II

알고리즘 분류 : 수학

 

x_(n+1) = (x_n + y_n) / 2, y_(n+1) = 2 x_n y_n / (x_n + y_n)이라는 점화식과 x_0, y_0의 값이 주어졌을 때 최종적으로 수렴하는 위치를 구하는 문제이다.

 

원래 문제의 의도는 점화식에서 식 관계를 정리하여 풀이하는 문제 같은데, 그냥 아래와 같이 반복문을 돌리면 풀린다.

문제 난이도가 비정상적으로 투표된 것 같아 더 낮은 난이도로 기여했다.

 

 

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

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

    double x, y; cin >> x >> y;

    for(int i=0; i<10000; i++) {
        double px = x, py = y;

        x = (px + py) / 2;
        y = 2 * px * py / (px + py);
    }

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

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

 

 

백준 BOJ 19939번 : 박 터뜨리기

문제 난이도 : Silver V

알고리즘 분류 : 그리디

 

N개의 공을 M개의 바구니에 나누어 담을 때, 각 바구니에 최소 1개 이상의 공이 들어있고 각 바구니에 들어있는 공의 수가 모두 다르도록 배치하면서 공이 가장 많이 든 바구니와 적게 든 바구니의 공 차이 수가 최소가 되도록 담을 때, 그 때의 차이를 구하는 문제이다.

 

M개의 바구니에 공을 담는데 필요한 최소한의 공의 수는 1, 2, 3, ... , M개의 공을 담았을 때이므로 M x (M+1) / 2개이다.

이것보다 공의 수가 적다면 -1을 출력해주면 된다.

이제 N에서 M x (M+1) / 2를 뺀 나머지에 대해서 생각해보면, 이들은 많이 담은 바구니부터 차례로 1개씩 공을 더 담아주면 된다.

만약 나머지가 M의 배수라면 모든 바구니에 똑같이 배분하면 되므로 가장 많이 든 바구니와 적게 든 바구니의 공의 수의 차이는 M개가 되고, 그렇지 않다면 M-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 N, M; cin >> N >> M;

    if(N < M * (M + 1) / 2) {
        cout << -1 << "\n";
        return 0;
    }

    int x = N - M * (M + 1) / 2;

    if(x % M == 0) cout << M - 1 << "\n";
    else cout << M << "\n";
}

 

 

백준 BOJ 16969번 : 차량 번호판 2

문제 난이도 : Silver V

알고리즘 분류 : 조합론

 

문자열이 주어지고 c가 있는 자리에는 a ~ z 중 하나의 문자가, d가 있는 자리에는 0 ~ 9 중 하나의 숫자가 들어간다고 하며 같은 문자나 숫자가 연속으로 나오면 안된다고 할 때 가능한 조합의 수를 구하는 문제이다.

 

앞 자리의 숫자나 문자가 결정되면 뒷 자리에서는 앞에 나온 숫자 또는 문자와만 겹치지 않으면 되므로, 앞에서부터 순서대로 배치하는 경우의 수를 곱해주면 된다.

 

 

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

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

    string str; cin >> str;

    int ans = 1;

    for(int i=0; i<str.length(); i++) {
        if(str[i] == 'c') {
            if(i == 0 || (i > 0 && str[i-1] != 'c')) ans *= 26;
            else ans *= 25;
        }
        else if(str[i] == 'd') {
            if(i == 0 || (i > 0 && str[i-1] != 'd')) ans *= 10;
            else ans *= 9;
        }

        ans %= (int)(1e9 + 9);
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 20104번 : Timecard

문제 난이도 : Bronze II

알고리즘 분류 : 문자열

 

문자열이 주어지면 모두 소문자로 바꾸는 함수를 구현하는 문제이다.

 

함수 구현 문제이므로 문제에서 제시한 조건에 맞게 함수를 완성해야 한다.

init 함수는 convert 함수가 몇 번 호출될 것인지를 입력하는 함수인데, 없어도 문제 풀이에 지장이 없으므로 그냥 둔다.

convert 함수만 구현해주면 되는데, 잘못된 선언을 사용하면 컴파일 에러가 날 수 있으니 주의해야 한다.

함수 구현 문제는 최대한 문제에서 준 코드를 건드리지 말고 작성하자.

 

 

#include "timecard.h"

static int N;

void init(int n) {
	N = n;
    
    return;
}

std::string convert(std::string s) {
	for(int i=0; i<s.length(); i++)
        if(s[i] >= 'A' && s[i] <= 'Z') s[i] += 'a' - 'A';
    
	return s;
}

 

 

백준 BOJ 13604번 : Jogo de Estratégia

문제 난이도 : Bronze II

알고리즘 분류 : 구현

 

N명의 플레이어가 M턴을 돌아가면서 경기를 하는데, 1번, 2번, ... , N번 순서대로 점수를 얻고 이 과정을 M번 반복한다.

점수를 가장 많이 얻은 플레이어를 구하는데, 만약 2명 이상인 경우 마지막에 점수를 얻은 플레이어가 우위라고 할 때 그 사람을 구하는 문제이다.

 

동점일 경우 점수를 마지막에 얻은 사람이 우선 순위라고 하였으므로 v[i] >= Max이면 답을 갱신할 수 있도록 조건식의 부등호에 등호를 붙여주자.

나머지 구현은 간단하다.

 

 

#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<int> v(N+1);

    int Max = 0, ans;

    for(int i=0; i<M; i++)
        for(int j=1; j<=N; j++) {
            int x; cin >> x;

            v[j] += x;

            if(v[j] >= Max) {
                Max = v[j];
                ans = j;
            }
        }

    cout << ans << "\n";
}

 

 

백준 BOJ 20761번 : Alloys

문제 난이도 : Bronze III

알고리즘 분류 : 수학

 

합금을 만들 때 세 금속의 비가 x:y:z (x+y+z = 1) 으로 들어간 경우 단위 무게 당 가격은 x+y, 경도는 xy라고 할 때 단위 무게당 가격을 c만큼 지불할 수 있을 때 얻을 수 있는 최대 경도를 구하는 문제이다.

 

x + y = k일 때 xy의 최댓값은 (k/2)^2이다.

다만 문제 조건에서 x+y+z = 1이고 x, y, z는 음수가 될 수 없으므로 x + y는 1을 넘을 수 없다.

따라서 1보다 큰 비용 c가 주어졌을 때에도 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);

    double x; cin >> x;

    x = min(x, 1.0);

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

    cout << pow(x/2, 2) << "\n";
}

 

 

백준 BOJ 11431번 : Mr. Gorbachev, Tear Down This Wall!

문제 난이도 : Bronze II

알고리즘 분류 : 기하학

 

N+1개의 점이 주어지고, i번째 점과 i+1번째 점을 잇는 선분으로 벽이 이어져있다고 할 때, 한 명이 길이 1만큼의 벽을 부수는데 걸리는 시간과 사람의 수가 주어지면 벽을 모두 부수는데 걸리는 시간을 구하는 문제이다.

 

1명이 길이 1만큼의 벽을 부수는데 걸리는 시간이 M이고, 벽을 부수는 사람이 K라면 길이 1의 벽을 부수는데 걸리는 시간은 M/K이다.

벽의 총 길이를 S라고 하면 정답은 S * M/K가 되는데, S는 단순 반복문으로 쉽게 구할 수 있으므로 아래와 같이 풀이하면 된다.

 

 

#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 T; cin >> T;

    for(int t=1; t<=T; t++) {
        int N, M, K; cin >> N >> M >> K;

        vector<pair<double, double>> v(N+1);

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

        double sum = 0;

        for(int i=1; i<N+1; i++) {
            if(v[i-1].first == v[i].first) sum += abs(v[i-1].second - v[i].second);
            else sum += abs(v[i-1].first - v[i].first);
        }

        int ans = ceil(sum * M / K);

        cout << "Data Set " << t << ":\n";
        cout << ans << "\n\n";
    }
}

 

 

백준 BOJ 10383번 : The Cost of Moving

문제 난이도 : Bronze II

알고리즘 분류 : 정렬

 

주어진 N개의 문자열을 정렬할 때, 각 문자열을 원래 위치에서 이동한 거리의 합을 구하는 문제이다.

예를 들어 3 1 2를 1 2 3으로 이동시켰다면, 1은 1만큼, 2는 1만큼, 3은 2만큼 이동했으므로 이동 거리의 합은 4가 된다.

 

문자열을 정렬하기 전 map으로 위치를 저장해놓고, 정렬 후 위치와 map 값의 차이의 합을 구해주면 쉽게 답을 얻을 수 있다.

 

 

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

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

    for(int t=1; ; t++) {
        int N; cin >> N;
        if(N == 0) break;

        vector<string> v(N);
        map<string, int> m;

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

            m[v[i]] = i;
        }

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

        int ans = 0;

        for(int i=0; i<N; i++) ans += abs(m[v[i]] - i);

        cout << "Site " << t << ": " << ans << "\n";
    }
}

 

 

백준 BOJ 9897번 : Lamp

문제 난이도 : Bronze II

알고리즘 분류 : 구현

 

N개의 램프가 번호순으로 있고, M명의 경비병의 이름과 해당 경비병이 램프를 끌 번호의 초항과 공차가 주어질 때, K개의 쿼리에 대해 해당 경비병이 초항과 공차에 대한 등차수열 번호들의 램프를 토글(꺼진 것은 켜고 켜진 것은 끔)할 때, 마지막에 켜져있는 램프의 수를 구하는 문제이다.

 

특정 알고리즘을 사용한다기보다는 문제에서 하라는 그대로 구현하면 되는 문제이다.

bool 벡터로 램프의 상태를 저장해주고, 또한 각 경비병에 대한 정보를 구조체를 이용한 벡터로 저장해주었다.

toggle은 v[i] = !v[i]와 같은 방식으로 간단하게 표현할 수 있다.

 

 

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

struct s { string a; int b, c; };

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

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

    vector<bool> v(N+1);

    vector<s> u(M);
    for(int i=0; i<M; i++)
        cin >> u[i].a >> u[i].b >> u[i].c;

    while(K--) {
        string str; cin >> str;

        for(int i=0; i<M; i++) {
            if(str == u[i].a) {
                for(int j=u[i].b; j<=N; j+=u[i].c) v[j] = !v[j];
            }
        }
    }

    int ans = 0;

    for(int i=1; i<=N; i++)
        if(v[i]) ans++;

    cout << ans << "\n";
}

 

 

백준 BOJ 11999번 : Milk Pails (Bronze)

문제 난이도 : Silver V

알고리즘 분류 : 브루트포스

 

용량이 N인 통과 M인 통으로, 반드시 통을 꽉 채워 용량이 K인 빈 통에 넣을 때, 최대한 채운 양을 구하는 문제이다.

 

브루트포스로 해결할 수 있지만, 시간을 줄이기 위해 N을 i=0부터 하여 i*N <= K일 때까지 반복문을 돌리면서, 나머지 양만큼을 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 N, M, K; cin >> N >> M >> K;

    int ans = 0;

    for(int i=0; i*N<=K; i++) {
        ans = max(ans, i*N + ((K - i*N)/M)*M);
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 5046번 : 전국 대학생 프로그래밍 대회 동아리 연합

문제 난이도 : Silver V

알고리즘 분류 : 구현

 

투숙객의 수, 예산, 호텔의 수, 선택할 수 있는 주가 주어지고 각 호텔에 따른 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 N, B, H, W; cin >> N >> B >> H >> W;

    int ans = INT_MAX;

    while(H--) {
        int p; cin >> p;

        bool check = false;

        for(int i=0; i<W; i++) {
            int x; cin >> x;

            if(x >= N) check = true;
        }

        if(check && p*N <= B) ans = min(ans, p*N);
    }

    if(ans != INT_MAX) cout << ans << "\n";
    else cout << "stay home\n";
}

 

 

---

이 글을 수정한 시각 이후로 8/8까지는 계속 외부 활동을 할 예정이어서 푼 문제가 글로 모두 정리되지 않을 수도 있다.

8/8 이후에 시간이 남는다면 "어려운 문제들 중에서" 풀이를 일부 정리해볼 생각이다.