백준 BOJ Gold 난이도 구현 외 다양한 문제들 풀이 220812

백준 BOJ 15683번 : 감시

문제 난이도 : Gold IV

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

 

1~5인 5종류의 감시 카메라가 있고 각 카메라는 네 방향 중 하나로 설치할 수 있으며, 6은 벽이라고 할 때 감시 카메라가 감시할 수 없는 블럭의 최소 수를 구하는 문제이다.

 

감시 카메라의 최대 개수가 8개 이하이므로, 8개의 감시 카메라를 모두 4방향에 대해 검사해도 4^8의 경우의 수밖에 나오지 않는다.

따라서 브루트포스로 모든 감시 카메라로 가능한 모든 방향의 배치를 돌려주면 된다.

나의 경우에는 8자리 이하의 4진수를 사용하여 각 자리수가 카메라의 방향이 되도록 구현하였다.

 

 

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

int N, M;
struct s { int t, x, y; };
vector<s> u;
vector<int> w;
vector<vector<int>> vv;

void f(int x, int y, int dir) {
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    while(true) {
        x += dx[dir], y += dy[dir];

        if(x < 0 || y < 0 || x >= N || y >= M) break;
        if(vv[x][y] == 6) break;

        vv[x][y] = -1;
    }
}

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

    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++) {
            cin >> v[i][j];

            if(v[i][j] >= 1 && v[i][j] <= 5) u.push_back({v[i][j], i, j});
        }

    w.resize(u.size());

    int ans = N*M;

    for(int i=0; i<pow(4, w.size()); i++) {
        int temp = i;

        for(int j=w.size()-1; j>=0; j--) {
            w[j] = temp % 4;

            temp /= 4;
        }

        vv.clear();
        vv = v;

        for(int j=0; j<u.size(); j++) {
            int x = u[j].x, y = u[j].y, t = u[j].t;

            if(t == 1) f(x, y, w[j]);
            else if(t == 2) {
                f(x, y, w[j]);
                f(x, y, (w[j] + 2) % 4);
            }
            else if(t == 3) {
                f(x, y, w[j]);
                f(x, y, (w[j] + 1) % 4);
            }
            else if(t == 4) {
                f(x, y, w[j]);
                f(x, y, (w[j] + 1) % 4);
                f(x, y, (w[j] + 2) % 4);
            }
            else if(t == 5) {
                f(x, y, w[j]);
                f(x, y, (w[j] + 1) % 4);
                f(x, y, (w[j] + 2) % 4);
                f(x, y, (w[j] + 3) % 4);
            }
        }

        int cnt = 0;

        for(int j=0; j<N; j++)
            for(int k=0; k<M; k++)
                if(vv[j][k] == 0) cnt++;

        ans = min(ans, cnt);
    }

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

 

 

백준 BOJ 17144번 : 미세먼지 안녕!

문제 난이도 : Gold IV

알고리즘 분류 : 구현, 시뮬레이션

 

N x M 배열에 각 먼지가 초마다 1/5씩 상하좌우로 퍼지고, 또한 공기 청정기의 바람 방향에 따라 먼지가 이동되며 공기 청정기가 있는 칸으로 들어오는 먼지들은 사라진다고 할 때 K초 후 전체 먼지의 양을 구하는 문제이다.

 

구현 문제답게 문제에서 하라는대로 기능을 구현하는 문제이다.

일단 각 배열 값을 그 배열 내에서 갱신하려고 하면 인접한 칸들 사이에 얼마씩 이동해야 하는지 계산이 안되므로, 2차원 배열 하나를 더 선언하여 이동할 값만 저장해주도록 하고 마지막에 더해줄 수 있도록 한다.

그리고 공기 청정기에 의한 이동은 반복문 8개를 써서 8방향으로 이동하는 먼지들을 모두 이동시켜주면 된다.

공기 청정기로 이동하는 먼지는 사라지므로 이를 빼먹지 않도록 주의한다.

 

 

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

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

    int r = -1;

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

            if(v[i][j] == -1 && r == -1) r = i;
        }

    while(K--) {
        vector<vector<int>> u(N, vector<int>(M));

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

                int cnt = 0;

                int di[4] = {1, -1, 0, 0};
                int dj[4] = {0, 0, 1, -1};

                for(int k=0; k<4; k++) {
                    int ni = i + di[k];
                    int nj = j + dj[k];

                    if(ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
                    if(v[ni][nj] == -1) continue;

                    u[ni][nj] += v[i][j] / 5;
                    cnt++;
                }

                u[i][j] -= cnt * (v[i][j] / 5);
            }

        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++) v[i][j] += u[i][j];

        for(int i=r-1; i>0; i--) v[i][0] = v[i-1][0];
        for(int i=0; i<M-1; i++) v[0][i] = v[0][i+1];
        for(int i=0; i<r; i++) v[i][M-1] = v[i+1][M-1];
        for(int i=M-1; i>1; i--) v[r][i] = v[r][i-1];

        v[r][1] = 0;

        for(int i=r+2; i<N-1; i++) v[i][0] = v[i+1][0];
        for(int i=0; i<M-1; i++) v[N-1][i] = v[N-1][i+1];
        for(int i=N-1; i>r+1; i--) v[i][M-1] = v[i-1][M-1];
        for(int i=M-1; i>1; i--) v[r+1][i] = v[r+1][i-1];

        v[r+1][1] = 0;
    }

    int ans = 0;

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            if(v[i][j] != -1) ans += v[i][j];

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

 

 

백준 BOJ 3055번 : 탈출

문제 난이도 : Gold IV

알고리즘 분류 : 구현, BFS

 

고슴도치가 1초에 1칸 상하좌우로 이동 가능하고, 모든 물은 상하좌우 모든 방향으로 1초에 1칸씩 퍼진다고 할 때, 고슴도치가 물을 피해 굴까지 도달하는 최단 시간을 구하는 문제이다.

 

BFS 문제인데, 핵심은 물의 이동 역시 BFS로 구현해야한다는 데에 있다.

해결책 중 하나는 물의 위치가 저장되어있는 큐를 하나 따로 구현하여, 1초마다 반복문을 돌 때마다 당시 큐의 크기만큼만 pop을 하여 해당 좌표의 상하좌우를 탐색하는 것이다.

그 다음 고슴도치의 위치 역시 1초에 이동할 수 있는 만큼만 pop을 해주어 상하좌우를 BFS 탐색 해주면 된다.

 

 

#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<char>> v(N, vector<char>(M));
    vector<vector<int>> dis(N, vector<int>(M, -1));

    queue<pair<int, int>> q, qq;

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

            if(v[i][j] == 'S') {
                dis[i][j] = 0;
                q.push({i, j});
            }
            else if(v[i][j] == '*') qq.push({i, j});
        }

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    while(!q.empty()) {
        int s = qq.size();

        while(s--) {
            int x = qq.front().first;
            int y = qq.front().second;
            qq.pop();

            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if(v[nx][ny] != '.' && v[nx][ny] != 'S') continue;

                v[nx][ny] = '*';
                qq.push({nx, ny});
            }
        }

        s = q.size();

        while(s--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if(v[x][y] == 'D') {
                cout << dis[x][y] << "\n";
                return 0;
            }

            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if((v[nx][ny] != '.' && v[nx][ny] != 'D') || dis[nx][ny] != -1) continue;

                dis[nx][ny] = dis[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    cout << "KAKTUS\n";
}

 

 

백준 BOJ 17213번 : 과일 서리

문제 난이도 : Silver II

알고리즘 분류 : 조합론

 

N 종류의 과일 중에서 모든 종류의 과일을 최소 1개 이상 훔치면서 총 M개의 과일을 훔치는 경우의 수를 구하는 문제이다.

 

중복 조합을 사용하여 풀이할 수 있는데, 중복 조합은 하나도 안 고르는 경우도 포함하므로, 상황을 약간 바꾸어 모든 과일은 무조건 1개 이상 훔칠 것이므로 이 1개씩 총 N개를 제외하여 N 종류 과일 중에서 M-N개의 과일을 0개 이상 훔치는 상황으로 생각하자.

그러면 중복 조합으로 경우의 수를 나타내어보면 N H M-N이 되는데, 이것은 (N + M - N + 1) C (M - N) = (M-1) C (N-1)이다.

M은 최대 30, N은 최대 10이므로 이를 고려하여 combination을 dp로 구해주면 된다.

 

 

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

int co[31][31] = {};

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

    for(int i=0; i<=30; i++) co[i][0] = 1;
    for(int i=1; i<=30; i++)
        for(int j=1; j<=30; j++) co[i][j] = co[i-1][j-1] + co[i-1][j];

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

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

 

 

백준 BOJ 25153번 : TiM

문제 난이도 : Silver V

알고리즘 분류 : 구현

 

계산기에 X, +, -, 숫자를 하나씩 입력할 때, 계산기에 나온 모든 한 자리 숫자의 합과, 연결된 숫자의 합, 그리고 수식이 0이 되기 위한 X의 값을 구하는 문제이다. (입력은 한 줄에 문자 하나씩 들어온다.)

 

한 자리 숫자의 합은 매 입력마다 숫자가 한 자리씩 들어오므로, 이들을 각자 더해주면 된다.

연결된 수들의 합은 string으로 숫자를 이어붙이다가, 부호가 들어오면 지금까지 입력된 숫자를 끊어서 합해주면 된다.

수식이 0이 되기 위한 X의 값을 구하기 위해서는 단순히 일차 방정식의 해를 구하는 과정대로 X의 총합과 숫자의 총합을 구하여, (숫자의 총합) / (X의 총합 x (-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;

    int a = 0, b = 0, c = 0, d = 0;
    char ch = '+';
    string num = "";

    while(M--) {
        char x; cin >> x;

        if(x == '+' || x == '-') {
            if(num != "") {
                if(ch == '+') b += stoi(num);
                else b -= stoi(num);

                d += abs(stoi(num));

                num = "";
            }

            ch = x;
        }
        else if(x == 'X') {
            if(ch == '+') a++;
            else a--;
        }
        else {
            c += x - '0';

            num += x;
        }
    }

    if(num != "") {
        if(ch == '+') b += stoi(num);
        else b -= stoi(num);

        d += abs(stoi(num));

        num = "";
    }

    cout << c << "\n";
    cout << d << "\n";
    cout << b / (-a) << "\n";
}

 

 

백준 BOJ 19874번 : Максимальное произведение

문제 난이도 : Silver V

알고리즘 분류 : 누적 합

 

배열의 중간을 나누어 두 개의 배열의 각 합의 곱이 최대가 되도록 하려면 몇 번째 원소 뒤에서 잘라야 하는지를 구하는 문제이다.

 

합이 일정한 두 수의 곱이 커지기 위해서는 두 원소의 크기가 비슷해야 한다.

따라서 누적 합 배열을 만들어 주고, v[i]와 v[N] - v[i]의 차가 가장 작은 지점의 i 뒤를 잘라주면 된다.

 

 

#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+1);

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

        v[i] = v[i-1] + x;
    }

    int Min = LLONG_MAX, idx;

    for(int i=1; i<=N; i++) {
        if(abs(v[i] - (v[N] - v[i])) < Min) {
            Min = abs(v[i] - (v[N] - v[i]));
            idx = i;
        }
    }

    cout << idx << "\n";
}

 

 

백준 BOJ 19971번 : Домашнее задание

문제 난이도 : Silver V

알고리즘 분류 : 그래프 이론

 

N개의 작업에 대해 각 작업의 수행 시간이 주어지고, 두 작업 중 먼저 해야하는 관계 M개가 주어질 때, 최대 1개의 업무를 하지 않아도 된다면 모든 업무를 마무리하는데 걸리는 최소 시간을 구하는 문제이다.

 

어떤 업무를 제외할 수 있는 경우는 다른 문제들이 그 문제를 거쳐서 갈 필요가 없는 경우이다.

따라서 adj 값이 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);

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

    vector<int> v(N+1);
    int sum = 0;

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

        sum += v[i];
    }

    vector<vector<int>> adj(N+1);

    while(M--) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
    }

    int Max = 0;

    for(int i=1; i<=N; i++) {
        if(adj[i].size() > 0) continue;

        Max = max(Max, v[i]);
    }

    int ans = sum - Max;

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

 

 

백준 BOJ 21533번 : Игральные кубики

문제 난이도 : Silver V

알고리즘 분류 : 사칙연산

 

양쪽 눈의 합이 7인 주사위를 던져서 한 명은 위에 나오는 점수, 한 명은 아래에 나오는 점수를 받는다고 할 때, 한 명의 점수가 주어지면 나머지 한 명이 받았을 점수로 최솟값과 최댓값을 구하는 문제이다.

 

최소인 경우는 모두 6이 나오고 6으로 나눈 나머지가 한 번 나오는 경우이다. (물론 6의 배수라면 나머지는  나오지 않는다.)

이 경우 N/6 + (7 - (N%6))이 답으로 얻어지는데, N이 6의 배수인 경우는 예외 처리를 해주어야 한다.

점수가 최대인 경우는 모두 1이 나온 경우로, 해당 횟수만큼 6이 나왔을 것이므로 N에 6을 곱해주면 된다.

 

 

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

    int x = N / 6;

    if(N % 6 != 0) x += 7 - (N % 6);

    cout << x << " " << N * 6 << "\n";
}

 

 

백준 BOJ 16148번 : Non-Violent Protests

문제 난이도 : Silver V

알고리즘 분류 : 정렬

 

N명의 사람이 각각 몇 명이 폭동을 일으켰을 때 가담할 것인지에 대한 숫자가 주어졌을 때, 폭동을 일으키는 총 사람 수를 구하는 문제이다.

 

순서를 생각해보면 a_i = 0인 사람이 가장 먼저 일으키고, 그 다음 a_i = 1 이하인 사람이 일으키고, 그 다음 a_i = 2 이하인 사람이 일으킨다.

즉, 0부터 시작해서 i 이하인 수를 가지는 수가 없을 때까지 폭동이 일어난다.

따라서 원소들을 정렬한 뒤 반복문을 돌려서 i 이하인 정수가 없을 때 i를 답으로 얻어주면 된다.

다만 모든 사람이 가담하는 경우 N이 답이 되므로 예외 처리를 해준다.

 

 

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

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

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

        int ans = N;

        for(int i=0; i<N; i++)
            if(v[i] > i) {
                ans = i;
                break;
            }

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

 

 

백준 BOJ 10194번 : Aligned Calender

문제 난이도 : Silver V

알고리즘 분류 : 구현

 

어떤 행성의 달력은 13개월이고 각 달에 28일까지 있을 때, 지구의 날짜를 이 행성의 날짜로 바꾸는 문제이다.

이 때 13월 28일을 넘어갈 경우 Holiday가 되며, 윤년을 고려해주어야 한다.

 

단순히 각 입력이 그 해의 몇 번째 날짜인지를 구하고, 이것을 28로 나눈 몫과 나머지를 적절히 활용하여 답을 구해주면 된다.

날짜 문제의 경우에는 실수를 주의하자.

 

 

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

    while(T--) {
        int a, b, c; cin >> a >> b >> c;

        int x = c;

        int v[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

        for(int i=1; i<b; i++) x += v[i];

        if(b >= 3 && ((a % 4 == 0 && a % 100 != 0) || a % 400 == 0)) x++;

        cout << a << "/" << b << "/" << c << " became ";

        if(x > 13*28) cout << "a HOLIDAY\n";
        else cout << a << "/" << (x-1)/28 + 1 << "/" << (x-1)%28 + 1 << "\n";
    }
}