#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int dist[20][20];
int dp[20][1<<16]; // [현재도시][방문한도시]
int N;
 
int solve(int cur, int visited)
{
    // 모든 마을 방문시 
    if(visited == (1 << N) - 1)
    {
        // 0번 마을로 다시 돌아갈 수 있을때 
        if(dist[cur][0] != 0)
        {
            return dist[cur][0];
        }
        // 그 코스는 불가능 하도록 만들기 위해 매우 큰 수를 return
        else
        {
            return 99999999;    
        }
    }
    
    if(dp[cur][visited] != -1)
    {
        return dp[cur][visited];
    } 
    
    dp[cur][visited] = 99999999;
    
    for(int i = 1; i < N; i++)
    {
        // i번째 지역을 방문한 경우 
        if(visited & (1 << i))
        {
            continue;
        }    
        
        // 해당 지역의 비용이 0인 경우 
        if(dist[cur][i] == 0)
        {
            continue;
        }
        
        dp[cur][visited] = min(dp[cur][visited], solve(i, visited | (1 << i)) + dist[cur][i]);
    } 
    
    return dp[cur][visited];
}
 
int main(void)
{
//    freopen("B2098_input.txt", "r", stdin);
    
    cin >> N; 
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> dist[i][j];    
        }
    }
    
    memset(dp, -1, sizeof(dp));
    
    // 0 →1 →2 →3 →4 →0  시작점이 0인 최소비용 루트가 있다고 가정해보자. 이 때 'A원'의 비용이 들었다면, 
    // 2 →3 →4 →0 →1 →2  시작점이 2인 최소비용 루트는 시작점과 관계없이 'A원'의 비용이 든다. 
    cout << solve(0, 1);
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > DP' 카테고리의 다른 글

[백준 12865] 평범한 배낭 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 1480] 보석 모으기 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.13
[백준 2294] 동전 2 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 2293] 동전 1 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B2294_input.txt", "r", stdin);
    
    int n, k;
    int dp[10010] = {0};
    int coin[10010];
    
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        cin >> coin[i]; 
    }
    
    for(int i = 0; i <= k; i++)
    {
        dp[i] = 99999999;
    }
    dp[0] = 0;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = coin[i]; j <= k; j++)
        {
            dp[j] = min(dp[j], dp[j-coin[i]] + 1);
        }
    }
    
    if(dp[k] == 99999999)
    {
        cout << "-1";
    }
    else
    {
        cout << dp[k];    
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > DP' 카테고리의 다른 글

[백준 1480] 보석 모으기 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.13
[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
[백준 2293] 동전 1 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B2293_input.txt", "r", stdin);
    
    int n, k;
    long long dp[10010] = {0};
    int coin[10010];
        
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        cin >> coin[i];
    }
 
    dp[0] = 1;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = coin[i]; j <= k; j++)
        {
            dp[j] = dp[j] + dp[j-coin[i]];
        }
    }
    
    cout << dp[k];
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > DP' 카테고리의 다른 글

[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
[백준 2294] 동전 2 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
[백준 9461] 파도반 수열(DP) (C/C++)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B11047_input.txt", "r", stdin);
    
    int N, sum;
    int coin[10];
    int ans = 0;
    
    cin >> N >> sum;
    
    for(int i = 0; i < N; i++)
    {
        cin >> coin[i];
    }
    
    sort(coin, coin+N, greater<int>());
 
    int coinIdx = 0;
    while(sum > 0)
    {
        if(sum >= coin[coinIdx])
        {
            sum -= coin[coinIdx];
            ans++;
        }
        else
        {
            coinIdx++;
        }
    }
    
    cout << ans;
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > Greedy' 카테고리의 다른 글

[백준 1343] 폴리오미노 (Greedy) (C/C++)  (0) 2019.12.30
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int shape;
}node;
 
char map[55][55];
int visited[55][55][2]; // 가로모양, 세로모양 
int N;
bool Move = false;
 
int first_B_x, first_B_y;
int first_E_x, first_E_y;
int mid_B_x, mid_B_y;
int mid_E_x, mid_E_y;
int B_shape;
int E_shape;
 
queue<node> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int check(int x, int y)
{
    for(int i = x-1; i <= x+1; i++)
    {
        for(int j = y-1; j <= y+1; j++)
        {
            if(safe(i, j) == 0)
            {
                return 0;
            }
            else if(safe(i, j) == 1)
            {
                if(map[i][j] == '1')
                {
                    return 0;
                }
            }
        }
    }
    
    return 1;
}
 
void BFS(int x, int y, int shape)
{
    visited[x][y][shape] = 1;
    q.push({x, y, shape});
    
    while(!q.empty())
    {
        x = q.front().x;
        y = q.front().y;
        shape = q.front().shape;
        q.pop();
        
        if(x == mid_E_x && y == mid_E_y && shape == E_shape)
        {
            Move = true;
            return;
        }
        
        // 상하좌우 
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visited[xpos][ypos][shape] == 0 && map[xpos][ypos] != '1')
            {
                // 가로 
                if(shape == 0)
                {
                    if(safe(xpos, ypos-1) == 1 && safe(xpos, ypos+1) == 1 && map[xpos][ypos-1] != '1' && map[xpos][ypos+1] != '1')
                    {
                        visited[xpos][ypos][shape] = visited[x][y][shape]+1;
                        q.push({xpos, ypos, shape});
                    }
                }
                // 세로 
                else if(shape == 1)
                {
                    if(safe(xpos-1, ypos) == 1 && safe(xpos+1, ypos) == 1 && map[xpos-1][ypos] != '1' && map[xpos+1][ypos] != '1')
                    {
                        visited[xpos][ypos][shape] = visited[x][y][shape]+1;
                        q.push({xpos, ypos, shape});
                    }
                }
            }
        }
        
        // 회전 
        if(check(x, y) == 1)
        {
            // 가로 -> 세로 
            if(shape == 0)
            {
                if(visited[x][y][1] == 0)
                {
                    visited[x][y][1] = visited[x][y][0]+1;
                    q.push({x, y, 1});
                }
            }
            // 세로 -> 가로 
            else if(shape == 1)
            {
                if(visited[x][y][0] == 0)
                {
                    visited[x][y][0] = visited[x][y][1]+1;
                    q.push({x, y, 0});
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1938_input.txt", "r", stdin);
 
    cin >> N;
    
    int find_mid_B = 1;
    int find_mid_E = 1;
    
    for(int i = 0; i < N; i++)
    {
        string input;
        cin >> input;
        
        for(int j = 0; j < N; j++)
        {
            map[i][j] = input[j];
            
            if(map[i][j] == 'B' && find_mid_B == 1)
            {
                first_B_x = i;
                first_B_y = j;
                
                find_mid_B++;
            }
            else if(map[i][j] == 'B' && find_mid_B == 2)
            {
                mid_B_x = i;
                mid_B_y = j;
                
                find_mid_B++;
            }
            
            if(map[i][j] == 'E' && find_mid_E == 1)
            {
                first_E_x = i;
                first_E_y = j;
                
                find_mid_E++;
            }
            else if(map[i][j] == 'E' && find_mid_E == 2)
            {
                mid_E_x = i;
                mid_E_y = j;
                
                find_mid_E++;
            }
        }
    }
    
    // 출발 통나무 - 가로 
    if(first_B_x - mid_B_x == 0)
    {
        B_shape = 0;
    }
    // 출발 통나무 - 세로 
    else if(first_B_x - mid_B_x == -1)
    {
        B_shape = 1;
    }
    
    // 도착 통나무 - 가로 
    if(first_E_x - mid_E_x == 0)
    {
        E_shape = 0;
    }
    // 도착 통나무 - 세로 
    else if(first_E_x - mid_E_x == -1)
    {
        E_shape = 1;
    }
    
    BFS(mid_B_x, mid_B_y, B_shape);
    
    if(Move == false)
    {
        cout << "0";
    }
    else
    {
        cout << visited[mid_E_x][mid_E_y][E_shape]-1;
    }
           
    return 0; 
}  
cs
저작자표시 (새창열림)

'Baekjoon > BFS' 카테고리의 다른 글

[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
[백준 1261] 알고스팟 (BFS) (C/C++) (★★)  (0) 2020.02.16
[백준 1167] 트리의 지름 (BFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 1967] 트리의 지름 (BFS, Tree) (C/C++)  (0) 2020.02.16
#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
 
vector<pair<int, int>> graph[510];
map<pair<int, int>, int> not_go;
vector<int> min_track[510];
int d[510];
int V, E, start, arrive;
 
void find_min_track(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    d[start] = 0;
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(nowCost != d[now])
        {
            continue;    
        }
        
        for(int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i].first;
            int nextCost = graph[now][i].second;
            
            if(nowCost + nextCost < d[next])
            {
                d[next] = nowCost + nextCost;
                pq.push({d[next], next});
                
                min_track[next].clear();
                min_track[next].push_back(now);
            }
            else if(nowCost + nextCost == d[next])
            {
                min_track[next].push_back(now);
            }
        }
    }
}
 
void find_semi_min_track(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    d[start] = 0;
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(nowCost != d[now])
        {
            continue;    
        }
        
        for(int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i].first;
            int nextCost = graph[now][i].second;
            
            if(not_go[{now, next}] == 1)
            {
                continue;
            }
            
            if(nowCost + nextCost < d[next])
            {
                d[next] = nowCost + nextCost;
                pq.push({d[next], next});
            }
        }
    }
}
 
void del_min_track(int node)
{
    if(node == start)
    {
        return;
    }
    
    for(int i = 0; i < min_track[node].size(); i++)
    {
        not_go[{min_track[node][i], node}] = 1;
        
        del_min_track(min_track[node][i]);
    }
}
 
int main(void)
{
//    freopen("B5719_input.txt", "r", stdin);
    
    while(1)
    {
        cin >> V >> E;
        
        if(V == 0 && E == 0)
        {
            break;
        }
        
        cin >> start >> arrive;
        
        for(int i = 0; i < V; i++)
        {
            d[i] = 199999999;
            graph[i].clear();
            min_track[i].clear();
        }
        not_go.clear();
    
        for(int i = 1; i <= E; i++)
        {
            int from, to, weight;
            cin >> from >> to >> weight;
            
            graph[from].push_back({to, weight});
        }
        
        find_min_track(start);
        del_min_track(arrive);
        
        for(int i = 0; i < V; i++)
        {
            d[i] = 199999999;
        }
        
        find_semi_min_track(start);
        
        if(d[arrive] == 199999999)
        {
            cout << "-1" << "\n";
        }
        else
        {
            cout << d[arrive] << "\n";
        }
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > Graph' 카테고리의 다른 글

[백준 6118] 숨바꼭질 (Dijkstra) (C/C++)  (0) 2020.05.17
[백준 16681] 등산 (Dijkstra) (C/C++) (★★)  (0) 2020.02.18
[백준 2211] 네트워크 복구 (Dijkstra) (C/C++)  (0) 2020.02.18
[백준 1504] 특정한 최단경로 (Floyd-Warshall) (C/C++)  (0) 2020.02.17
[백준 1238] 파티 (Floyd-Warshall) (C/C++)  (0) 2020.02.17
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
#define INF 1000000000000
 
vector<pair<int, int>> graph[100010];
long long d_up[100010];
long long d_down[100010];
int height[100010];
int V, E;
int happy, strength;
 
void dijkstra_up(int start)
{
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, start});
    d_up[start] = 0;
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        long long nowCost = pq.top().first;
        pq.pop();
        
        if(nowCost != d_up[now])
        {
            continue;    
        }
        
        for(int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i].first;
            long long nextCost = graph[now][i].second;
            
            if(height[now] < height[next])
            {
                if(nowCost + nextCost < d_up[next])
                {
                    d_up[next] = nowCost + nextCost;
                    pq.push({d_up[next], next});    
                }    
            }    
        }
    }
}
 
void dijkstra_down(int start)
{
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, start});
    d_down[start] = 0;
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        long long nowCost = pq.top().first;
        pq.pop();
        
        if(nowCost != d_down[now])
        {
            continue;    
        }
        
        for(int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i].first;
            long long nextCost = graph[now][i].second;
            
            if(height[now] < height[next])
            {
                if(nowCost + nextCost < d_down[next])
                {
                    d_down[next] = nowCost + nextCost;
                    pq.push({d_down[next], next});
                }    
            }    
        }
    }
}
 
int main(void)
{
//    freopen("B16681_input.txt", "r", stdin);
    
    cin >> V >> E >> strength >> happy;
    
    for(int i = 1; i <= V; i++)
    {
        cin >> height[i];
        
        d_up[i] = INF;
        d_down[i] = INF;
    }
 
    for(int i = 1; i <= E; i++)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        
        graph[from].push_back({to, weight});
        graph[to].push_back({from, weight});
    }
    
    dijkstra_up(1);
    dijkstra_down(V);
    
    long long Max = -INF;
    for(int i = 2; i < V; i++)
    {
        if(Max < happy*height[i] - strength*d_up[i] - strength*d_down[i])
        {
            Max = happy*height[i] - strength*d_up[i] - strength*d_down[i];
        }
    }
    
    if(Max == -INF)
    {
        cout << "Impossible";
    }
    else
    {
        cout << Max;    
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > Graph' 카테고리의 다른 글

[백준 6118] 숨바꼭질 (Dijkstra) (C/C++)  (0) 2020.05.17
[백준 5719] 거의 최단경로 (Dijkstra) (C/C++) (★★★)  (0) 2020.02.19
[백준 2211] 네트워크 복구 (Dijkstra) (C/C++)  (0) 2020.02.18
[백준 1504] 특정한 최단경로 (Floyd-Warshall) (C/C++)  (0) 2020.02.17
[백준 1238] 파티 (Floyd-Warshall) (C/C++)  (0) 2020.02.17
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int, int>> graph[1010];
vector<int> track[1010];
int d[1010];
int V, E;
int lineCnt;
 
void dijkstra(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    d[start] = 0;
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(nowCost != d[now])
        {
            continue;    
        }
        
        for(int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i].first;
            int nextCost = graph[now][i].second;
            
            if(nowCost+nextCost < d[next])
            {
                d[next] = nowCost+nextCost;
                pq.push({d[next], next});
                
                track[next].clear();
                track[next].push_back(now);
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2211_input.txt", "r", stdin);
    
    cin >> V >> E;
    
    for(int i = 1; i <= V; i++)
    {
        d[i] = 199999999;
    }
 
    for(int i = 1; i <= E; i++)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        
        graph[from].push_back({to, weight});
        graph[to].push_back({from, weight});
    }
    
    dijkstra(1);
    
    for(int i = 1; i <= V; i++)
    {
        lineCnt += track[i].size();
    }
    
    cout << lineCnt;
    
    for(int i = 1; i <= V; i++)
    {
        for(int j = 0; j < track[i].size(); j++)
        {
            cout << i << " "  << track[i][j];
        }
        cout << "\n";
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > Graph' 카테고리의 다른 글

[백준 5719] 거의 최단경로 (Dijkstra) (C/C++) (★★★)  (0) 2020.02.19
[백준 16681] 등산 (Dijkstra) (C/C++) (★★)  (0) 2020.02.18
[백준 1504] 특정한 최단경로 (Floyd-Warshall) (C/C++)  (0) 2020.02.17
[백준 1238] 파티 (Floyd-Warshall) (C/C++)  (0) 2020.02.17
[백준 1916] 최소비용 구하기 (Dijkstra) (C/C++)  (0) 2020.02.16

+ Recent posts

티스토리툴바