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

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

1. 문제설명

인접한 노드 두개가 우수마을이 되면 안된다.

그리고 자신이 우수마을이 아니라면 인접한 노드 중 적어도 하나가 우수마을이 되어야한다.

문제를 해결하기 위해

노드를 재귀적으로 탐색해야한다.

현재 노드가 우수마을인 경우와 우수마을이 아닌 경우를 나눈다.

그리고 현재 노드가 우수마을인 경우에는 다음 노드는 무조건 우수마을이면 안된다.

현재 노드가 우수마을이 아닌 경우에는 다음 노드는 우수마을이거나 우수마을이 아닐 수 있다.

이 때

현재 우수마을이 아닌데 다음 마을도 우수마을이 아닌 경우 문제가 생길 수 있다고 생각했다.

예를 들어 세개의 노드가 다 우수마을이 아닌 경우라면 문제의 조건에 맞지 않다.

하지만 다음 코드와 같이 재귀적으로 탐색하면서 최댓값을 계속 넘겨주다보면

모든 마을이 우수마을이 아닌 경우는 남지 않아서 괜찮다.

최댓값만 남기기 때문에 모든 마을이 우수마을이 아닌 경우는 살아남을 수 없다.

2.문제풀이코드 C++

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

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

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

    for(int i=0; i<adj[node].size(); i++){
        int nx = adj[node][i];
        if(vis[nx]) continue;

        DFS(nx);
        dp[node][0] += max(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=1; i<=N; i++){
        cin >> people[i];
    }

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

    DFS(1);
    cout << max(dp[1][0], dp[1][1]) << '\n';
    return 0;
}