딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/1941

1. 문제설명

25명의 학생 중 7명을 뽑아보는 백트래킹을 진행하면서

7명 중 4명이상이 S인지 확인하고,

7명이 모두 인접해있는지 BFS 탐색을 해서

옳으면 경우의 수를 추가해주면 된다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int ans = 0;
string arr[5];
bool student[25];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool check() {
    int num = 0;
    int x, y;
    
    for (int i = 0; i < 25; i++) {
        if (student[i]) {
            int row = i / 5;
            int col = i % 5;

            if (arr[row][col] == 'S') {
                num++;
                x = row;
                y = col;
            }

        }
    }
    if (num < 4) return false;
    
    queue<pair<int, int> > Q;
    Q.push({x, y});
    int cnt = 1;

    bool vis[5][5] = {0};
    vis[x][y] = 1;

    while (!Q.empty()) {
        int curx = Q.front().first;
        int cury = Q.front().second;
        Q.pop();

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

            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5)continue;
            if (vis[nx][ny]) continue;
            if (!student[nx * 5 + ny]) continue;

            vis[nx][ny] = 1;
            Q.push({nx, ny});
            cnt++;
        }
    }


    return cnt == 7;
}


void DFS(int idx, int num) {
    if (num == 7) {
        if (check()) {
            ans++;
        }
        return;
    }

    for (int i = idx; i < 25; i++) {
        student[i] = 1;
        DFS(i + 1, num + 1);
        student[i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 5; i++) {
        cin >> arr[i];
    }

    DFS(0, 0);
    cout << ans << '\n';

    return 0;
}

https://www.acmicpc.net/problem/2749

#include <bits/stdc++.h>

using namespace std;
const int mod =1'000'000;
struct Fibo{
    long long arr[2][2] = {{1, 1}, {1,0}};

    Fibo(){
        arr[0][0] = 1;
        arr[0][1] = 1;
        arr[1][0] = 1;
        arr[1][1] = 0;
    };

    Fibo mutiple(Fibo b){
        long long tmp[2][2] = {{0, 0}, {0, 0}};
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    tmp[i][k] += (arr[i][j] * b.arr[j][k])%mod;
                    tmp[i][k] %= mod;
                }
            }
        }

        Fibo ret = Fibo();
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                ret.arr[i][j] = tmp[i][j];
            }
        }

        return ret;
    }

    void baseMultiple(){
        long long res[2][2] = {{0,0}, {0, 0}};
        long long tmp[2][2] = {{1, 1}, {1,0}};
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    res[i][k] += (arr[i][j] * tmp[j][k])%mod;
                    res[i][k] %= mod;
                }
            }
        }

        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                arr[i][j] = res[i][j];
            }
        }
    }
};

int cnt = 0;
long long N;
Fibo doubleSquare(Fibo cur, long long n){
    if(n==1){
        return cur;
    }

    Fibo tmp = doubleSquare(cur, n/2);
    Fibo ret = tmp.mutiple(tmp);

    if(n%2){
        ret.baseMultiple();
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    Fibo st = Fibo();

    Fibo fb = doubleSquare(st, N);

    cout << fb.arr[1][0] << '\n';
    return 0;
}

1. 문제설명

보석에는 무게와 가격이 존재하고,

각 가방마다 챙길 수 있는 최대 무게가 존재합니다.

그리고 각 가방에는 최대 하나의 보석만 넣을 수 있습니다.

이러한 조건이 있을 때 도둑이 여러 개의 가방을 통해 챙길 수 있는 보석들의 가격의 최대 합을 구해야합니다.

우선 각 가방마다 챙길 수 있는 보석의 최대 무게가 다른 조건을 생각해보면,

가방의 최대 무게가 크면 여러개의 보석을 선택할 수 있고,

가방의 최대 무게가 작으면 선택할 수 있는 보석이 줄어듭니다.

이를 바탕으로 최대 무게가 작은 가방부터 보석을 선택해나가면 됩니다.

그리고 각 가방이 챙길 수 있는 최대 무게의 보석을 챙겨야 합니다.

이를 위해서 현재 가방의 최대 무게를 바탕으로

현재 가방에 담을 수 있는 보석을 우선순위 큐에 넣고,

더이상 담을 수 있는 보석이 없다면 우선순위 큐에서 가격이 가장 큰 보석을 꺼내서 선택하는 방식으로 문제를 해결할 수 있습니다.

정리하면

배낭을 최대 무게를 바탕으로 오름차순으로 정렬하고,

보석을 무게를 바탕으로 오름차순으로 정렬해서

배낭의 무게를 작은 값부터 돌면서

무게가 작은 보석부터 넣을 수 있는 보석을 우선순위 큐에 넣고,

더이상 넣을 수 없다면 우선순위 큐에서 가격이 가장 큰 보석을 꺼내서 답에 더해주는 것을 반복하면 됩니다.

이렇게 하면

항상 가방은 해당 가방이 선택할 수 있는 보석의 최대 가격을 선택하게 됩니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int n, k;

struct Jew{
    int m, v;
    bool operator<(const Jew& a) const {
        return v < a.v;
    }
};

vector<pair<int,int> > jew;
vector<int> backpack;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    long long ans = 0;

    for(int i=0; i<n; i++){
        int m, v;
        cin >> m >> v;

        jew.push_back({m,v});
    }

    for(int i=0; i<k; i++){
        int c;
        cin >> c;
        backpack.push_back(c);
    }

    sort(jew.begin(), jew.end());
    sort(backpack.begin(), backpack.end());

    int ptr = 0;

    priority_queue<Jew> pq;

    for(int i=0; i<k; i++){

        while(ptr<n && jew[ptr].first <= backpack[i]){
            pq.push({jew[ptr].first, jew[ptr].second});
            ptr++;
        }

        if(!pq.empty()){
            ans += pq.top().v;
            pq.pop();
        }

    }


    cout << ans << '\n';
    return 0;
}

https://www.acmicpc.net/problem/10830

#include <bits/stdc++.h>

using namespace std;

long long N, B;

struct Matrix {
    int arr[6][6] = {0};
};

Matrix multiple(Matrix m1, Matrix m2) {
    Matrix tmp;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                tmp.arr[i][k] += (m1.arr[i][j] * m2.arr[j][k]) % 1000;
                tmp.arr[i][k] %= 1000;
            }
        }
    }
    return tmp;
}

Matrix power(Matrix A, long long b) {
    if (b == 1) return A;

    Matrix powered = power(A, b / 2);
    Matrix ret = multiple(powered, powered);
    if (b % 2 == 1) {
        ret = multiple(ret, A);
    }
    return ret;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> B;

    Matrix matrix, ans;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> matrix.arr[i][j];
        }
    }

    ans = power(matrix, B);

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << ans.arr[i][j] % 1000 << ' ';
        }
        cout << '\n';
    }


    return 0;
}

https://www.acmicpc.net/problem/1300

숫자 범위가 굉장히 크다.

하나씩 다 따져보다간 시간이 너무 오래 걸린다.

바운더리 컨디션을 생각해보면서 이분탐색을 시행해야 문제를 해결 할 수 있다.

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

int n, k;

int main() {

    cin >> n >> k;

    int st = 1, en = k , ans;

    while(st <= en){
        int mid = (st + en)/2;

        int cnt = 0;
        for(int i=1; i<=n; i++){
            cnt += min(n, mid/i);
        }

        if(cnt >= k){
            ans = mid;
            en = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }

    cout << ans << '\n';


    return 0;
}

https://www.acmicpc.net/problem/2213

1. 문제설명

서로 인접하지 않은 노드의 집합 중 합이 가장 큰 집합을 찾아야하는 문제이다.

트리를 순회하면서 각 노드마다 선택된 상태와 선택되지 않은 상태를 나누어서 DP로 문제를 해결해야한다.

이 문제에서는 독립집합의 노드를 모두 구해야하는데 이 부분이 어렵다

독립집합의 노드를 구하는 방법은

1. 현재 노드를 택한 경우가 택하지 않은 경우보다 결괏값이 커야한다.

2. 다시 트리를 순회하면서 이전 노드와 인접하지 않은 노드를 구해야한다.

1, 2번을 모두 만족시키는 노드를 골라야 정답이 된다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
#define MX 10001

int n, weight[MX], dp[MX][2];
vector<int> adj[MX];
bool vis[MX];
vector<int> Path;

void DFS(int node) {
    vis[node] = 1;
    dp[node][1] = weight[node];

    for (auto nx: adj[node]) {
        if (vis[nx]) continue;

        DFS(nx);
        dp[node][1] += dp[nx][0];
        dp[node][0] += max(dp[nx][0], dp[nx][1]);

    }
}

void tracing(int cur, int pre){
    if(dp[cur][1] > dp[cur][0] && !vis[pre]){
        vis[cur] = 1;
        Path.push_back(cur);
    }

    for(auto nx: adj[cur]){
        if(nx==pre) continue;
        tracing(nx, cur);
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }

    int a, b, cnt = 0;

    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    DFS(1);
    memset(vis, 0 , sizeof(vis));
    tracing(1,0);
    sort(Path.begin(), Path.end());


    cout << max(dp[1][0], dp[1][1]) << '\n';
    for(auto num: Path){
        cout << num << ' ';
    }

    return 0;
}

https://www.acmicpc.net/problem/2533

#include <bits/stdc++.h>
using namespace std;
#define MX 1000001


int N, dp[MX][2];
vector<int> adj[MX];
bool vis[MX];

void DFS(int node){
    vis[node] = 1;

    dp[node][0] = 1;
    for(auto nx : adj[node]){
        if(vis[nx]) continue;
        DFS(nx);

        dp[node][0] += min(dp[nx][0], dp[nx][1]);
        dp[node][1] += dp[nx][0];
    }
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    for(int i=0; i<N-1; i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    DFS(1);

    cout << min(dp[1][0], dp[1][1]) << '\n';


    return 0;
}

https://www.acmicpc.net/problem/15681

#include <bits/stdc++.h>
using namespace std;
#define MX 100001

int N, R, Q, dp[MX];
vector<int> adj[MX];
bool vis[MX];

int DFS(int node){
    dp[node] = 1;

    for(int i=0; i<adj[node].size(); i++){
        if(dp[adj[node][i]]==0)
            dp[node] += DFS(adj[node][i]);
    }

    return dp[node];
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N >> R >> Q;
    for(int i=0; i<N-1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    DFS(R);

    for(int i=0; i<Q; i++){
        int num;
        cin >> num;
        cout << dp[num] << '\n';
    }

    return 0;
}