면빈면빈면빈면빈

[적용한 알고리즘]

DP

[아이디어]

중복을 없애주기 위해, 

첫번째 동전을 이용하는 경우를 다 더해주고,

두번째 동전을 이용하는 경우를 다 더해주고,

세번째 동전을 이용하는 경우를 다 더해주고,

쭉쭉 더해주면 된다.

[교훈]

중복 없애는 테크닉이 상당히 아름다웠다.

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;


int main(){
    int t;
    scanf("%d", &t);

    while (t--){
        int N, M;
        int dp[10001] = { 0 };
        scanf("%d", &N);

        int coin[21] = { 0 };

        for (int i = 0; i < N; i++){
            scanf("%d", coin + i);
        }

        sort(coin, coin + N);
        scanf("%d", &M);

        dp[0] = 1;

        for (int i = 0; i < N; i++){
            for (int j = coin[i]; j <= M; j++){
                dp[j] += dp[j - coin[i]];
            }
        }

        printf("%d\n", dp[M]);
    }
    return 0;
}

[적용한 알고리즘]

DP

[아이디어]

재귀를 이용하는 dp의 기본형이다.  long long!

<코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

long long dp[68];
long long Koong(int n){
    long long &ret = dp[n];

    if (n < 2) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    if (ret != -1) return ret;
    
    return ret = Koong(n - 1) + Koong(n - 2) + Koong(n - 3) + Koong(n - 4);
}

int main(){
    int t;
    scanf("%d", &t);

    while (t--){
        int N;
        scanf("%d", &N);
        memset(dp, -1, sizeof(dp));
        printf("%lld\n", Koong(N));
    }

    return 0;
}

[적용한 알고리즘]

DP

[아이디어]

DP[지난 시간][이동한 횟수][현재 있는 나무]

그리고 자두가 떨어지는 위치를 입력한 배열을 a[] 라고 했을 때,

현재 시간을 i,

움직인 횟수를 j,

현재 있는 나무가 1번 혹은 2번 이면,

1. a[i] = 1 인 경우

1-1) 1번 나무에 위치한 경우 (받아먹는 경우)

dp[i][j][1] = max(받아먹기 위해 2번에서 이동한 경우, 그대로 1번에 있던 경우) + 1 

102) 2번 나무에 위치한 경우 (이번엔 받아먹지 않기로 한 경우)

dp[i][j][2] = dp[i - 1][j][2]

2. a[i] = 2 인 경우

2-1) 2번 나무에 위치한 경우 (받아먹는 경우)

dp[i][j][2] = max(받아먹기 위해 1번에서 이동한 경우, 그대로 1번에 있던 경우) + 1

2-2) 1번 나무에 위치한 경우 (이번엔 받아먹지 않기로 한 경우)

dp[i][j][1] = dp[i - 1][j][1]

[교훈]

여기서 반드시 신경 써줘야하는 경우가 j = 0 (한번도 안움직이는 경우) 이다.

j - 1 이 음수가 되는 경우를 (j = 0) 신경안써주고 코드 썼다가 피똥쌌다.

j = 0 인 경우도 분류 해줘야한다.

찾는데 한참 걸렸다..

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int T, W;
    scanf("%d %d", &T, &W);

    int a[1001];
    for (int i = 1; i <= T; i++){
        scanf("%d", &a[i]);
    }

    int dp[1001][31][3] = { 0 };
    if (a[1] == 1) dp[1][0][1] = 1;
    if (a[1] == 2) dp[1][1][2] = 1;

    for (int i = 2; i <= T; i++){
        for (int j = 0; j <= W; j++){
            if (a[i] == 1){
                if (j == 0){
                    dp[i][0][1] = dp[i - 1][0][1] + 1;
                    continue;
                }
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][2]) + 1;
                dp[i][j][2] = dp[i - 1][j][2];
            }
            if (a[i] == 2){
                if (j == 0){
                    dp[i][0][1] = dp[i - 1][0][1];
                    continue;
                }
                dp[i][j][1] = dp[i - 1][j][1];
                dp[i][j][2] = max(dp[i - 1][j - 1][1], dp[i - 1][j][2]) + 1;
            }
        }
    }

    int ans = -1;
    for (int i = 0; i <= W; i++){
        ans = max(ans, max(dp[T][i][1], dp[T][i][2]));
    }

    printf("%d", ans);

    return 0;
}

[적용한 알고리즘]

DP

[아이디어]

분류할까?

ㅋㅋㅋㅋ

[교훈]

끈기와 인내

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX = 305;

int dp[MAX][MAX][MAX];
int N;

int main(){
    scanf("%d", &N);
    dp[0][0][0] = 1;
    for (int x = 0; x <= N; x++){
        for (int y = 0; y <= N; y++){
            for (int z = 0; z <= N; z++){
                dp[x][y][z] %= 1000000;
                if (x == y) dp[x + 2][y + 2][z] += dp[x][y][z];
                if (y == z) dp[x][y + 2][z + 2] += dp[x][y][z];
                if (y == z + 1) dp[x][y + 2][z + 2] += dp[x][y][z];
                if (x == y + 1) dp[x + 2][y + 2][z] += dp[x][y][z];
                if (x == y && z == y + 1) dp[x + 1][y + 2][z + 1] += dp[x][y][z];
                if (z == y + 1) dp[x][y + 2][z + 2] += dp[x][y][z];
                if (y == x + 1) dp[x + 2][y + 2][z] += dp[x][y][z];
                if (y == z && x == y + 1) dp[x + 1][y + 2][z + 1] += dp[x][y][z];
                if (y == z + 1) dp[x][y + 1][z + 3] += dp[x][y][z];
                if (x == y + 1) dp[x + 1][y + 3][z] += dp[x][y][z];
                if (x == y && y == z) dp[x + 1][y + 2][z + 1] += dp[x][y][z];
                if (z == y + 1) dp[x][y + 3][z + 1] += dp[x][y][z];
                if (y == x + 1) dp[x + 3][y + 1][z] += dp[x][y][z];
                if (x == z && y + 1 == x) dp[x + 1][y + 2][z + 1] += dp[x][y][z];
                if (z + 2 == y) dp[x][y + 1][z + 3] += dp[x][y][z];
                if (y + 2 == x) dp[x + 1][y + 3][z] += dp[x][y][z];
                if (x + 1 == y && y == z) dp[x + 2][y + 1][z + 1] += dp[x][y][z];
                if (x == y) dp[x + 3][y + 1][z] += dp[x][y][z];
                if (y == z) dp[x][y + 3][z + 1] += dp[x][y][z];
                if (x == y && y == z) dp[x + 1][y + 1][z + 2] += dp[x][y][z];
                if (x + 2 == y) dp[x + 3][y + 1][z] += dp[x][y][z];
                if (y + 2 == z) dp[x][y + 3][z + 1] += dp[x][y][z];
                if (x == y && z + 1 == y) dp[x + 1][y + 1][z + 2] += dp[x][y][z];
                if (y == z) dp[x][y + 1][z + 3] += dp[x][y][z];
                if (x == y) dp[x + 1][y + 3][z] += dp[x][y][z];
                if (x == y && y == z) dp[x + 2][y + 1][z + 1] += dp[x][y][z];
            }
        }
    }
    printf("%d\n", dp[N][N][N]);
    return 0;
}

[적용한 알고리즘]

DP, 비트마스크

[아이디어]

http://kks227.blog.me/220787042377 를 참고했습니다.

[생각의 흐름 / 절차] 

내용

[교훈]

비트마스킹을 이용한 것은 알겠으나, 코드가 정확하게 와닿지는 않는다. 더 공부해야겠다.

<코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int IMPOSSIBLE = 1000000000;

int N, W[16][16], dp[16][1 << 16];

int TSP(int current, int visited){
    //Base Case : 전부 방문한 경우
    if (visited == (1 << N) - 1){
        if (W[current][0] != 0) return W[current][0];
        return IMPOSSIBLE;
    }

    int &ret = dp[current][visited];
    if (ret != -1) return ret;


    ret = IMPOSSIBLE;
    for (int i = 0; i < N; i++){
        if (visited & (1 << i) || W[current][i] == 0) continue;
        ret = min(ret, TSP(i, visited | (1 << i)) + W[current][i]);
    }

    return ret;
}
int main(){
    scanf("%d", &N);
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            scanf("%d", &W[i][j]);
        }
    }

    memset(dp, -1, sizeof(dp));
    printf("%d\n", TSP(0, 1));

    return 0;
}

[적용한 알고리즘]

DP

[아이디어]

N 이 어마어마하게 큰데, 필요한 배열의 개수는 

log2 10^12 이기 때문에 그리 많지 않다. 

따라서 map 을 이용하면 될 것이다. 

[생각의 흐름 / 절차] 

내용

[교훈]

내용

<코드>

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
typedef long long lld;

map<lld, lld> dp;
lld N, P, Q;

lld go(lld i){
    if (i == 0) return 1;
    if (dp[i] > 0) return dp[i];
    return dp[i] = go(i / P) + go(i / Q);
}

int main(){
    scanf("%lld %lld %lld", &N, &P, &Q);
    printf("%lld", go(N));
    return 0;
}

[적용한 알고리즘]

DP

[아이디어]

얼핏 보면 2^N 돌아야할 것 같아 불가능해보였다. 

그래서 한참 고민하다가, 상근이가 아는 숫자 x의 범위가 0<=x<=20 라는 걸 알고 더 고민했다. 

그래서

dp[i][j] = i 번째 숫자까지 봤을 때 j 를 만들 수 있는 경우의 수

0 <= i < N 이고,  0 <= j <= 20 이므로 시간 문제가 없다. 

입력 받은 숫자의 배열을 a[] 라고 하면,

dp[i][j] = dp[i - 1][j - a[i]] + dp[i - 1][j + a[i]] 이다 .

i - 1 번째 숫자에서 j 가 되기 위해서는

a[i]를 더해주는 경우가 있을 것이고,

a[i]를 빼주는 경우가 있을 것이기 때문이다. 

그래서 범위를 고려해 코드를 짤 수 있다. 

[생각의 흐름 / 절차] 

내용

[교훈]

DP는 다채롭다. 힘든 과정인 것 같다. 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

long long dp[101][21];

int main(){
    int N;
    scanf("%d", &N);
    N--;
    vector<int> a(N);
    for (int i = 0; i < N; i++){
        scanf("%d", &a[i]);
    }

    int goal;
    scanf("%d", &goal);

    dp[0][a[0]] = 1;

    for (int i = 1; i < N; i++){
        for (int j = 0; j <= 20; j++){
            if (j - a[i] >= 0){
                dp[i][j] += dp[i - 1][j - a[i]];
            }
            if (j + a[i] <= 20){
                dp[i][j] += dp[i - 1][j + a[i]];
            }
        }
    }

    printf("%lld\n", dp[N - 1][goal]);
    return 0;
}

[적용한 알고리즘]

DP

[아이디어]

앞선 게시물 기지국과 거의 같은 방식으로 접근했다. 

구획을 연속적으로 진행하므로, 

dp[i] = max(dp[j - 1] + (i ~ j 까지 조 짜기 점수)) 로 해줬다. 

[생각의 흐름 / 절차] 

[교훈]

DP는 풀수록 모르겠다ㅋㅋ

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int dp[1001];
int main(){
    int N;
    scanf("%d", &N);

    vector<int> score(N + 1);
    for (int i = 1; i <= N; i++){
        scanf("%d", &score[i]);
    }

    for (int i = 1; i <= N; i++){
        int Max = -1;
        int Min = 10001;

        for (int j = i; j >= 1; j--){
            Max = max(score[j], Max);
            Min = min(score[j], Min);

            int res = Max - Min;

            dp[i] = max(dp[j - 1] + res, dp[i]);
        }
    }

    printf("%d\n", dp[N]);
    return 0;
}

[적용한 알고리즘]

DP

[아이디어]

dp[i] : i 번째 건물까지 지었을 때 비용의 최솟값

으로 정해놓고 생각하자,

[생각의 흐름 / 절차] 

dp[i] = min(dp[i], dp[j - 1] + cost) 이고

cost : j ~ i 까지 기지국 비용

[교훈]

내용

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int n; scanf("%d", &n);
    vector<pair<int, int>> P(n + 1);

    for (int i = 1; i <= n; i++){
        scanf("%d %d", &P[i].first, &P[i].second);
        if (P[i].second < 0){
            P[i].second *= -1;
        }
    }

    sort(P.begin() + 1, P.end());
    vector<int> dp(n + 1, 100000000);
    dp[0] = 0;

    for (int i = 1; i <= n; i++){
        int up = 0;
        for (int j = i; j >= 1; j--){
            up = max(up, P[j].second); // 다 커버쳐야하니까
            int square = max(P[i].first - P[j].first, up * 2);
            dp[i] = min(dp[i], dp[j - 1] + square);
        }
    }

    printf("%d\n", dp[n]);
    return 0;
}

[적용한 알고리즘]

다익스트라

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

잠이 안와서 푸는 기본문제2

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int MAX_V = 20001;
const int INF = 1000000000;
typedef pair<int, int> P;

int main(){
    int t; scanf("%d", &t);

    while (t--){
        int V, E, K;
        vector<P> adj[MAX_V];
        scanf("%d %d %d", &V, &E, &K);

        for (int i = 0; i < E; i++){
            int from, to, cost;
            scanf("%d %d %d", &to, &from, &cost);
            adj[from].push_back(P(to, cost));
        }

        int dist[MAX_V];
        fill(dist, dist + MAX_V, INF);
        bool visited[MAX_V] = { 0 };
        priority_queue<P, vector<P>, greater<P>> PQ;

        dist[K] = 0;
        PQ.push(P(0, K));

        while (!PQ.empty()){
            int cur;
            do {
                cur = PQ.top().second;
                PQ.pop();
            } while (!PQ.empty() && visited[cur]);

            if (visited[cur]) break;

            visited[cur] = true;
            for (auto &p : adj[cur]){
                int nxt_node = p.first;
                int nxt_cost = p.second;

                if (dist[nxt_node] > dist[cur] + nxt_cost){
                    dist[nxt_node] = dist[cur] + nxt_cost;
                    PQ.push(P(dist[nxt_node], nxt_node));
                }
            }
        }
        int ans_cnt = 0;
        int ans_time = -1;

        for (int i = 1; i <= V; i++){
            if (dist[i] == INF) continue;
            ans_cnt++;
            ans_time = max(ans_time, dist[i]);
        }

        printf("%d %d\n", ans_cnt, ans_time);
    }
    return 0;
}