백준 BOJ 풀이 : 다양한 유형 및 백트래킹 문제들 220731

백준 BOJ 12199번 : Password Attacker (Large)

문제 난이도 : Gold III

알고리즘 분류 : 조합론 (+ 포함-배제의 원리)

 

N자리 비밀번호를 M종류 문자를 모두 사용하여 만들 수 있는 조합의 수를 구하는 문제이다.

 

 

 

위와 같이 먼저 N자리 비밀번호를 M종류 이하의 문자들을 사용하여 만드는 경우의 수에서, M-1종류 이하의 문자들을 사용하여 조합할 수 있는 경우의 수를 빼고, 또 M-2종류 이하의 문자들을 조합하여 만들 수 있는 경우를 더해주고, ...를 반복해주면 된다. (by 포함과 배제의 원리)

다만 이 문제에서 거듭 제곱과 모듈로 처리가 귀찮은데, 특히 모듈로의 경우 반복문 중간에 값이 음수로 넘어갈 수 있으므로 이를 적절히 처리해주어야 한다.

 

 

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

int co[101][101] = {};
int mod = (int)(1e9 + 7);

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

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

    int T; cin >> T;

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

        int ans = 0;

        for(int i=0; i<M; i++) {
            int a;

            if(i % 2 == 0) a = 1;
            else a = -1;

            int b = 1;
            for(int j=0; j<N; j++) b = (b * (M - i)) % mod;

            ans = (ans + a * b * co[M][i] + mod*100) % mod;
        }

        cout << "Case #" << t << ": " << ans << "\n";
    }
}

 

여담으로 이 문제를 풀면 백준 BOJ 12198번 : Password Attackers (Small) 문제를 동일한 소스 코드로 AC를 받을 수 있다.

 

 

백준 BOJ 15591번 : MooTube (Silver)

문제 난이도 : Gold V

알고리즘 분류 : BFS

 

N개 동영상 사이 연관도 N-1개가 주어져 트리 관계를 만들 때, 어떤 영상을 시청했을 때 몇 개의 연관을 거쳐 연관된 동영상들 중 가장 작은 연관도가 k 이상인 영상의 수를 구하는 문제이다.

 

먼저 주어진 그래프의 정보를 통해 그래프를 형성해줄 수 있다.

그 다음 BFS와 비슷하게 탐색을 수행하는데, 도중에 k 값보다 작은 연관도 관계인 영상이 있다면 그 방향으로는 탐색을 중지해주며 방문하는 노드의 수만큼 count 해주면 된다.

 

 

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

    for(int i=0; i<N-1; i++) {
        int a, b, c; cin >> a >> b >> c;

        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

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

        vector<bool> vis(N+1);
        vis[b] = true;

        queue<int> q;
        q.push(b);

        int ans = 0;

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

            for(int i=0; i<adj[x].size(); i++) {
                int y = adj[x][i].first;

                if(vis[y]) continue;
                if(adj[x][i].second < a) continue;

                vis[y] = true;
                q.push(y);
                ans++;
            }
        }

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

 

 

백준 BOJ 17025번 : Icy Perimeter

문제 난이도 : Gold V

알고리즘 분류 : 그래프 탐색

 

2차원 배열이 주어질 때 가장 큰 # 덩어리의 면적을 구하고, 그 때의 둘레를 구하는 문제이다.

단, 면적이 가장 큰 덩어리가 여러 개라면 그 중 가장 둘레가 작은 것을 고른다.

 

일반적인 그래프 탐색 알고리즘으로 해결할 수 있는 문제이다.

면적의 경우 그래프 탐색을 수행하면서 배열 밖을 벗어나거나, 인접한 배열이 #이 아닌 경우 둘레 + 1로 카운트 해주면 된다.

 

 

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

int N, a, b, ma = 0, mb = 0;
vector<vector<char>> v;
vector<vector<bool>> vis;

void f(int x, int y) {
    vis[x][y] = true;
    a++;

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

    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 >= N) {
            b++;
            continue;
        }
        if(v[nx][ny] != '#') {
            b++;
            continue;
        }
        if(vis[nx][ny]) continue;

        f(nx, ny);
    }
}

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

    cin >> N;

    v.resize(N, vector<char>(N));

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

    vis.resize(N, vector<bool>(N));

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {
            if(v[i][j] != '#' || vis[i][j]) continue;

            a = 0, b = 0;

            f(i, j);

            if(a > ma || (a == ma && b < mb)) {
                ma = a;
                mb = b;
            }
        }

    cout << ma << " " << mb << "\n";
}

 

 

백준 BOJ 11964번 : Fruit Feast

문제 난이도 : Gold V

알고리즘 분류 : BFS

 

포만감 0에서 시작하여 최대치가 N이고, +a 또는 +b의 연산을 취하거나 최대 1번 물을 마셔 포만감을 절반 후 내림으로 만들 수 있다고 할 때 도달할 수 있는 최대 포만감을 구하는 문제이다.

 

BFS를 활용하여 모든 경우의 수를 탐색해볼 수 있다.

문제는 물을 최대 1번만 마실 수 있다는 것인데, 이것은 그냥 처음부터 2차원 벡터를 만들어서 뒷 칸의 값이 0이면 물을 아직 안 마신 것, 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, a, b; cin >> N >> a >> b;

    vector<vector<bool>> vis(N+1, vector<bool>(2));
    vis[0][0] = true;

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

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

        if(x + a <= N && !vis[x + a][y]) {
            vis[x + a][y] = true;
            q.push({x + a, y});
        }
        if(x + b <= N && !vis[x + b][y]) {
            vis[x + b][y] = true;
            q.push({x + b, y});
        }
        if(y == 0 && !vis[x/2][y + 1]) {
            vis[x/2][y + 1] = true;
            q.push({x/2, y + 1});
        }
    }

    int ans = 0;
    for(int i=0; i<=N; i++)
        if(vis[i][0] || vis[i][1]) ans = i;

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

 

 

백준 BOJ 6220번 : Making Change

문제 난이도 : Silver II

알고리즘 분류 : DP

 

M개의 서로 다른 종류의 동전 몇 개를 써서 N원을 만들 때 필요한 최소 동전 수를 구하는 문제이다.

 

DP를 이용하여 1원부터 그 금액을 만들 수 있는 최소 동전 수를 갱신시켜 나가면서 N원까지 그 답을 구하면 된다.

0 <= j < M인 동전 금액 v[j]에 대해 dp[i] = min(dp[i], dp[i - v[j]] + 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<int> v(M);
    for(int i=0; i<M; i++) cin >> v[i];

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

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

    for(int i=1; i<=N; i++)
        for(int j=0; j<M; j++)
            if(v[j] < i) dp[i] = min(dp[i], dp[i - v[j]] + 1);

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

 

 

백준 BOJ 14615번 : Defend the CTP!!

문제 난이도 : Gold V

알고리즘 분류 : 그래프 탐색

 

1번 노드에서 x번 노드를 방문한 뒤 N번 노드로 이동할 수 있는지의 여부를 구하는 문제이다.

 

쿼리가 1개라면 DFS를 2번 하여 풀이하면 되겠지만, 여기서는 쿼리가 최대 10만 개 들어올 수 있으므로 미리 방문 가능 여부를 다 구해두어야 한다.

 

따라서 정방향 그래프와 역방향 그래프 2개를 만든 뒤, bool 벡터 하나에는 1번 노드에서 방문할 수 있는 노드들을 구해놓고, 나머지 하나에는 N번 노드에서 역방향 그래프를 통해 방문할 수 있는 노드들을 구해놓자.

이제 각 쿼리에 대해 v[x] && u[x]이면 경로가 존재함을 O(1) 시간에 확인할 수 있게 됨으로써 문제가 풀린다.

 

 

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

vector<vector<int>> adj1, adj2;
vector<bool> v, u;

void f(int x) {
    v[x] = true;

    for(int i=0; i<adj1[x].size(); i++) {
        int y = adj1[x][i];

        if(!v[y]) f(y);
    }
}

void g(int x) {
    u[x] = true;

    for(int i=0; i<adj2[x].size(); i++) {
        int y = adj2[x][i];

        if(!u[y]) g(y);
    }
}

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

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

    adj1.resize(N+1);
    adj2.resize(N+1);

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

        adj1[a].push_back(b);
        adj2[b].push_back(a);
    }

    v.resize(N+1);

    f(1);

    u.resize(N+1);

    g(N);

    int K; cin >> K;

    while(K--) {
        int x; cin >> x;

        if(v[x] && u[x]) cout << "Defend the CTP\n";
        else cout << "Destroyed the CTP\n";
    }
}

 

 

백준 BOJ 16198번 : 에너지 모으기

문제 난이도 : Silver I

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

 

N개의 일렬로 놓여진 구슬 중 가장자리가 아닌 하나씩을 순서대로 선택하여, 양 옆 가장 가까운 구슬의 값을 곱하여 점수에 합하고 그 구슬을 제거하는 과정을 반복할 때, 점수의 최댓값을 구하는 문제이다.

 

구슬을 제거하는 순서의 경우의 수는 가장자리 2개를 제외한 나머지들의 순열의 개수이므로, (N-2)!가지이다.

N이 최대 10이므로 next_permutaion 함수를 활용하여 모든 경우의 수를 탐색해주기만 하면 된다.

구슬의 번호를 다시 매길 필요 없이 매 과정마다 제거한 구슬의 값을 0으로 만들고, 이후 값이 0인 칸은 무시하고 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; cin >> N;

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

    int ans = 0;

    vector<int> u(N-2);
    for(int i=0; i<N-2; i++) u[i] = i + 1;

    while(true) {
        vector<int> w(v);

        int sum = 0;

        for(int i=0; i<u.size(); i++) {
            w[u[i]] = 0;

            int cur = u[i], a = 0, b = 0;

            while(w[cur] == 0) cur--;
            a = w[cur];

            cur = u[i];

            while(w[cur] == 0) cur++;
            b = w[cur];

            sum += a * b;
        }

        ans = max(ans, sum);

        if(!next_permutation(u.begin(), u.end())) break;
    }

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

 

 

백준 BOJ 6374번 : To the Max

문제 난이도 : Silver II

알고리즘 분류 : 누적 합

 

주어진 2차원 배열에 대해 최대 구간 합 직사각형을 구하는 문제이다.

 

전형적인 누적 합 문제로, 2차원 누적 합 배열을 만들어주고, 4중 for문을 통해 직사각형의 위 아래 왼쪽 오른쪽을 잡아 그 범위의 직사각형 구간 합을 누적 합을 적절히 활용해서 표현해주면 된다.

 

 

#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<vector<int>> v(N+1, vector<int>(N+1));
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) cin >> v[i][j];

    vector<vector<int>> u(N+1, vector<int>(N+1));
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            u[i][j] = u[i-1][j] + u[i][j-1] + v[i][j] - u[i-1][j-1];

    int ans = INT_MIN;

    for(int i=1; i<=N; i++)
        for(int j=i; j<=N; j++)
            for(int k=1; k<=N; k++)
                for(int l=k; l<=N; l++)
                    ans = max(ans, u[j][l] - u[i-1][l] - u[j][k-1] + u[i-1][k-1]);

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

 

 

백준 BOJ 6187번 : Going to the Movies

문제 난이도 : Silver IV

알고리즘 분류 : 브루트포스 (+ 비트마스킹)

 

N마리 소의 무게가 M이 넘어가지 않도록 하는 최대 부분 합을 구하는 문제이다.

 

N이 16 이하이므로, 2^N가지 경우를 모두 시도해보면 된다. (각 소에 대해서 포함시킬지 안 시킬지를 결정)

나의 경우에는 비트마스킹을 활용하여 i를 1 이상 2^N 미만에 대해 i의 j번째 비트가 1이면 j번째 소를 포함시키는 식으로 하여 모든 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 M, N; cin >> M >> N;

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

    int ans = 0;

    for(int i=1; i<(1<<N); i++) {
        int sum = 0;

        for(int j=0; j<N; j++)
            if(i & (1 << j)) sum += v[j];

        if(sum <= M) ans = max(ans, sum);
    }

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

 

 

백준 BOJ 6977번 : Pattern Generator

문제 난이도 : Silver IV

알고리즘 분류 : 백트래킹

 

N과 M이 주어졌을 때 N자리의 0과 1로 이루어진 문자열 중 1이 M개인 문자열들을 사전순의 역순으로 출력하는 문제이다.

 

N자리 벡터의 앞의 M자리에 1을 넣어주고, prev_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);

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

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

        cout << "The bit patterns are\n";

        while(true) {
            for(int i=0; i<N; i++) cout << v[i];

            cout << "\n";

            if(!prev_permutation(v.begin(), v.end())) break;
        }

        cout << "\n";
    }
}

 

 

백준 BOJ 12204번 : Parentheses Order (Small)

문제 난이도 : Silver IV

알고리즘 분류 : 백트래킹

 

N쌍의 괄호로 이루어진 올바른 괄호 문자열 중에서, 사전순으로 나열했을 때 M번째 문자열을 구하는 문제이다.

 

이 문제 역시 크기가 N*2인 벡터에 앞의 절반은 '('로, 나머지는 ')'로 배치해준 뒤 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);

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        cout << "Case #" << t << ": ";

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

        vector<char> v(N*2);
        for(int i=0; i<N; i++) v[i] = '(';
        for(int i=N; i<N*2; i++) v[i] = ')';

        int idx = 1;
        bool fans = false;

        while(true) {
            bool check = true;
            int cnt = 0;

            for(int i=0; i<v.size(); i++) {
                if(v[i] == '(') cnt++;
                else cnt--;

                if(cnt < 0) check = false;
            }

            if(!check) {
                if(!next_permutation(v.begin(), v.end())) break;
                else continue;
            }

            if(idx == M) {
                for(int i=0; i<v.size(); i++) cout << v[i];
                cout << "\n";

                fans = true;
                break;
            }

            idx++;

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

        if(!fans) cout << "Doesn't Exist!\n";
    }
}

 

 

백준 BOJ 19949번 : 영재의 시험

문제 난이도 : Silver III

알고리즘 분류 : 백트래킹

 

10개의 5지선다 문제가 주어지고, 세 문제를 연속한 번호로 찍지 않는다고 할 때, 5개 이상 맞히는 경우의 수를 구하는 문제이다.

 

단순히 모든 경우에 대해 즉 (1, 1, 1, ... , 1)부터 (5, 5, 5, ... , 5)까지 돌리면서 연속한 3개의 수가 없으면서 5개 이상 맞은 경우를 count 해주면 된다.

참고로 문자열로 접근할 경우 시간이 오래 걸려 TLE를 받으니 정수로 처리하는 것이 좋다.

 

 

#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> v(10);
    for(int i=0; i<10; i++) cin >> v[i];

    int ans = 0;

    for(int i=0; i<pow(5, 10); i++) {
        int temp = i;

        vector<int> u(10);

        for(int j=0; j<10; j++) {
            u[j] = temp % 5 + 1;
            temp /= 5;
        }

        bool check = true;
        for(int j=2; j<10; j++)
            if(u[j] == u[j-1] && u[j-1] == u[j-2]) check = false;

        if(!check) continue;

        int cnt = 0;

        for(int j=0; j<10; j++)
            if(v[j] == u[j]) cnt++;

        if(cnt >= 5) ans++;
    }

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

 

 

백준 BOJ 12033번 : 김인천씨의 식료품가게 (Small), 백준 BOJ 12034번 : 김인천씨의 식료품가게 (Large)

문제 난이도 : Silver V

알고리즘 분류 : 구현

 

N개의 원가와 N개의 75% 가격의 숫자들이 섞여 있을 때, 할인된 숫자들 N개만 골라서 출력하는 문제이다.

 

작은 가격부터 체크하면서 이 가격의 4/3의 값을 가지는 다른 가격이 있는지 확인해주면 된다.

만약 있다면 둘 모두를 체크하고 (다른 번호로) 뒤로 넘어가면서 다른 것들도 동일하게 확인해준다.

탐색이 끝난 이후 할인된 가격에 해당하는 값으로 체크된 숫자들만 출력하면 된다.

 

 

#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*2);
        for(int i=0; i<N*2; i++) cin >> v[i];

        vector<int> u(N*2);

        for(int i=0; i<N*2; i++) {
            if(v[i] % 3 == 0 && u[i] == 0) {
                for(int j=i+1; j<N*2; j++) {
                    if(v[j] == v[i] / 3 * 4 && u[j] == 0) {
                        u[i] = 1;
                        u[j] = 2;

                        break;
                    }
                }
            }
        }

        cout << "Case #" << t << ": ";

        for(int i=0; i<N*2; i++)
            if(u[i] == 1) cout << v[i] << " ";

        cout << "\n";
    }
}

 

 

백준 BOJ 9934번 : 완전 이진 트리

문제 난이도 : Silver I

알고리즘 분류 : 트리

 

트리의 inorder traversal이 주어졌을 때, 트리 구조를 복구하는 문제이다.

 

inorder traversal의 경우 부모 노드 번호를 중심으로 왼쪽과 오른쪽에 동일한 개수의 왼쪽 자식 그룹, 오른쪽 자식 그룹이 존재하고 이것이 재귀적으로 존재하므로, 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);

    int N; cin >> N;

    vector<int> v((1 << N) - 1);

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

    vector<bool> u(v.size());

    for(int i=0; i<N; i++) {
        for(int j=(1 << (N-i-1)) - 1; j<v.size(); j+=(1 << (N-i-1))) {
            if(!u[j]) {
                cout << v[j] << " ";
                u[j] = true;
            }
        }
        cout << "\n";
    }
}

 

 

백준 BOJ 17212번 : 달나라 토끼를 위한 구매대금 지불 도우미

문제 난이도 : Silver III

알고리즘 분류 : DP

 

1, 2, 5, 7원의 4가지 동전이 있을 때 합으로 N원을 표현하기 위한 최소 동전 개수를 구하는 문제이다.

 

dp를 활용하여 1원부터 시작하여 누적해가며 답을 구하면 된다.

v[j]를 각 화폐 단위라고 했을 때 dp[i] = min(dp[i], dp[i - v[j]] + 1)이라는 점화식이 성립하므로 이에 대해 2중 for문을 사용해주면 된다.

 

 

#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> dp(N+1, INT_MAX);
    dp[0] = 0;

    int v[4] = {1, 2, 5, 7};

    for(int i=1; i<=N; i++)
        for(int j=0; j<4; j++)
            if(v[j] <= i) dp[i] = min(dp[i], dp[i - v[j]] + 1);

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

 

 

백준 BOJ 10320번 : Button Bashing

문제 난이도 : Silver II

알고리즘 분류 : BFS

 

0초에서 시작하여 N가지 종류의 버튼을 눌러 전자레인지 시간을 M초로 맞추되, M초로 맞추는 것이 불가능하다면 M초보다 크면서 M과 가장 가까운 시간을 맞추는 최소 버튼 횟수를 구하는 문제이다.

 

BFS로 풀이할 수 있으며, 문제 조건에 0초 미만으로 내려갈 경우 0초로, 3600초 초과로 올라갈 경우 3600초로 설정된다고 하는 조건을 놓치면 안된다.

 

 

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

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

        vector<int> dis(3601, -1);
        dis[0] = 0;

        queue<int> q;
        q.push(0);

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

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

                if(y < 0) y = 0;
                else if(y > 3600) y = 3600;

                if(dis[y] != -1) continue;

                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }

        int cur = M;
        while(dis[cur] == -1) cur++;

        cout << dis[cur] << " " << cur - M << "\n";
    }
}

 

 

백준 BOJ 2780번 : 비밀번호

문제 난이도 : Silver I

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

 

비밀번호 버튼이 있는 그림이 주어지고, 서로 상하좌우로 인접한 버튼만 눌러 N자리 비밀번호를 만드는 조합의 수를 구하는 문제이다.

 

백준 BOJ 12850번 : 본대 산책 2 문제와 비슷하게 풀이하면 된다.

인접한 버튼끼리 간선으로 연결해주고, dp로 누적하면서 그 합을 구해주면 된다.

 

 

#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 dp[1001][10] = {{}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};

    for(int i=2; i<=1000; i++) {
        vector<int> v(10);

        v[0] = dp[i-1][7];
        v[1] = dp[i-1][2] + dp[i-1][4];
        v[2] = dp[i-1][1] + dp[i-1][3] + dp[i-1][5];
        v[3] = dp[i-1][2] + dp[i-1][6];
        v[4] = dp[i-1][1] + dp[i-1][5] + dp[i-1][7];
        v[5] = dp[i-1][2] + dp[i-1][4] + dp[i-1][6] + dp[i-1][8];
        v[6] = dp[i-1][3] + dp[i-1][5] + dp[i-1][9];
        v[7] = dp[i-1][0] + dp[i-1][4] + dp[i-1][8];
        v[8] = dp[i-1][5] + dp[i-1][7] + dp[i-1][9];
        v[9] = dp[i-1][6] + dp[i-1][8];

        for(int j=0; j<10; j++) dp[i][j] = v[j] % 1234567;
    }

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        int ans = 0;
        for(int i=0; i<10; i++) ans = (ans + dp[N][i]) % 1234567;

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