2515 전시장

백준 2515 전시장 https://www.acmicpc.net/problem/2515

문제가 좀 까다로워 보인다. 그림을 배치하는데 세로 기준으로 보이는 부분이 S이상인 것에 대해서만 구입을 해서 최대화 시켜야한다. N의 범위또한 상당히 크다.

하지만 문제를 단순화 시키면 풀만한 문제이다.
사실상 그림이 가려진다는것은 그 그림을 배치하지 않는다는것과 동치이다.

따라서 그림을 높이순으로 오름차순, 가격을 내림차순으로 정렬한 후 [1, N] 구간의 그림을 선택하는 문제로 바뀐다.

DP를 적용시키고 높이 차이가 S이상인 지점을 찾는것은 이분탐색으로 찾으면 된다.

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Paint{     int v, h; }; bool cmp(const Paint &a, const Paint &b){     if (a.h == b.h)         return a.v > b.v;     return a.h < b.h; } Paint paint[300001]; int N, S; int dp[300001][2];     int diff[300001]; int binary_search(int n){     int l = 0, r = n - 1;          while (l <= r){         int mid = (l + r) / 2;         if (paint[n].h - paint[mid].h >= S) l = mid + 1;         else r = mid - 1;     }     return r; } int main(){     scanf("%d%d", &N, &S);     for (int n = 1; n <= N; n++)         scanf("%d%d", &paint[n].h, &paint[n].v);       sort(paint + 1, paint + N + 1, cmp);     paint[0].h = paint[0].v;       for (int n = 1; n <= N; n++){                 if (paint[n].h - dp[n - 1][1] >= S){            //차이가 S이상일때는 바로 더함             dp[n][0] = dp[n - 1][0] + paint[n].v;             dp[n][1] = paint[n].h;         }         else{             int prev;        // n과의 높이 차이가 S이상인 지점             prev = binary_search(n);             if (dp[n - 1][0] > dp[prev][0] + paint[n].v){ //현재 그림과 더했지만 유지되는 가치가 더 클 때                 dp[n][0] = dp[n - 1][0];                 dp[n][1] = dp[n - 1][1];             }             else{                                         //현재 그림과 높이차이가 가장 작게나는 가치가 더 클 때                 dp[n][0] = dp[prev][0] + paint[n].v;                 dp[n][1] = paint[n].h;             }         }     }     printf("%d\n", dp[N][0]);     return 0; } Colored by Color Scripter

cs

3948 홍준이의 친위대

백준 3948 홍준이의 친위대 https://www.acmicpc.net/problem/3948

<유사문제>
1146 지그재그 서기 https://www.acmicpc.net/problem/1146

1. 맨 앞줄에는 아무나 설 수 있다.
2. 둘째 줄에도 아무나 설 수 있다.
3. 셋째 줄에는 둘째 줄에 서 있는 사람이 첫째 줄에 서 있는 사람보다 클 경우, 둘째 줄에 서 있는 사람보다 작은 사람만이 설 수 있으며, 둘째 줄에 서 있는 사람이 첫째 줄에 서 있는 사람보다 작을 경우, 둘째 줄에 서 있는 사람보다 큰 사람만이 설 수 있다.
4. 넷째 줄부터는 둘째 줄과 셋째 줄을 비교하는 식으로 해서 N번째의 줄을 서는 사람은 N-2번째 줄과 N-1번째 줄에 서는 사람을 비교해서 세운다.

N명의 학생이 존재할 때 다음의 규칙을 따른다. 사실 이 말은 지그재그로 학생을 배치하는 것이다.

문제는 학생의 위치를 저장할 때 bitmask dp나 방문배열로 확인할 수 가 없다. (N이 100이하이므로)

그래서 다른 방법으로 접근해야하는데 바로 현재상태에서 작은사람과 큰사람의 수를 저장하며 비교하는것이다.

#include <cstdio> #include <cstring> #define mod 1000000 int N; int dp[111][111][2]; // 현재 사람보다 작은사람이 S, 큰사람이 L명 있을 때  // flag(1 : 더 큰사람을 골라야하는 경우, 0 : 더 작은 사람을 골라야하는 경우) int solve(int L, int S, int flag){             int range = L + S;     if (range == 0) return 1;          int &ret = dp[L][S][flag];     if (ret != -1) return ret;     ret = 0;     if (!flag)        //S을 골라야함         for (int i = 0; i < S; i++)             ret += solve(range - (i + 1), i, 1), ret %= mod;     else         for (int i = 0; i < L; i++)             ret += solve(i, range - (i + 1), 0), ret %= mod;     return ret % mod; } int main(){     memset(dp, -1, sizeof(dp));     scanf("%d", &N);     if (N == 1){         printf("1\n");         return 0;     }     int ans = 0;     for (int n = 0; n < N; n++){         ans += solve(n, N - 1 - n, 0);         ans %= mod;         ans += solve(n, N - 1 - n, 1);         ans %= mod;     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

(Dijkstra - 최단 경로 추적하기) 5719 거의 최단경로

백준 5719 거의 최단경로https://www.acmicpc.net/problem/5719
Codeground 캠퍼스와 도로(1) https://www.codeground.org/practice/practiceProblemView
Codeground 캠퍼스와 도로(2) https://www.codeground.org/practice/practiceProblemView
2325 개코전쟁 https://www.acmicpc.net/problem/2325
2307 도로검문 https://www.acmicpc.net/problem/2307
14554 The Other Way https://www.acmicpc.net/problem/14554
LG CNS 2017 Codemonster E번

어떤 지점으로부터의 최단거리를 알고싶으면 다익스트라 알고리즘을 사용하면 된다.

그 최단거리까지 이동하는 경로를 파악하는 방법은 2가지가 많이 사용된다.

1). 다익스트라 알고리즘이 끝나고 BFS돌리기
시작정점을 queue에 넣고 $dist[next]$ == $dist[here]$ + $adj[here][next]$인 경우에 
queue를 삽입하는 것을 반복한다.

다익스트라 알고리즘자체에서 최단경로를 갱신하는 방법과 유사하다.

2). 다익스트라 알고리즘을 돌리며 저장하기
$dist[next]$ == $dist[here]$ + $adj[here][next]$인 경우에 prev배열에 저장한다.
$dist[next]$ > $dist[here]$ + $adj[here][next]$인 경우에는 새로 갱신됬을 수 있으니 
prev배열을 초기화한 후 저장한다.

1. 5719 거의 최단경로 
최단경로를 구해서 다 지운후 다음 최단경로를 구한다.

#include <cstdio> #include <vector> #include <queue> #include <functional> #include <algorithm> using namespace std; #define INF 987654321 int N, M, S, D; vector<vector<pair<int, int>>> adj, rev; vector<vector<bool>> visit; vector<int> dist; void di(int start, int end){     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;     fill(dist.begin(), dist.end(), INF);     dist[start] = 0;     pq.push({ 0, start });     while (!pq.empty()){         int here = pq.top().second;         pq.pop();         for (auto n : adj[here]){             int next = n.second;             int cost = n.first + dist[here];             if (dist[next] > cost && visit[here][next]){                 dist[next] = cost;                 pq.push({ dist[next], next });             }         }     } } void bfs(int start, int end){     queue<int> q;     q.push(end);     while (!q.empty()){         int here = q.front();         q.pop();         if (here == start) continue;         for (auto n : rev[here]){             int next = n.second;                          if (dist[here] == dist[next] + n.first){                 visit[next][here] = false;                 q.push(next);             }         }     } } int main(){     while (scanf("%d%d", &N, &M), !(N == 0 && M == 0)){         adj = vector<vector<pair<int, int> > >(N, vector<pair<int, int>>());         rev = vector<vector<pair<int, int> > >(N, vector<pair<int, int>>());         visit = vector<vector<bool> >(N, vector<bool>(N, true));         dist = vector<int>(N, INF);         scanf("%d%d", &S, &D);         for (int m = 0; m < M; m++){             int u, v, d;             scanf("%d%d%d", &u, &v, &d);             adj[u].push_back({ d, v });             rev[v].push_back({ d, u });         }         di(S, D);         bfs(S, D);         di(S, D);         if (dist[D] != INF) printf("%d\n", dist[D]);         else printf("-1\n");     }     return 0; } Colored by Color Scripter

cs

2. 캠퍼스와 도로(1)
통행료를 징수하는 지점은 시작정점과 도착정점을 제외한 최단경로의 정점들이다.

#include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <functional> using namespace std; #define INF 987654321 int N, M; int ans; vector <vector<pair<int, int> > > adj;        //cost, to vector<int> dist; vector<bool> visit; void dijkstra(int start){     priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;     dist[start] = 0;     pq.push(make_pair(0, start));     while (!pq.empty()){         int here = pq.top().second;         pq.pop();         for (auto n : adj[here]){             int next = n.second;             int ncost = n.first + dist[here];             if (dist[next] > ncost){                 dist[next] = ncost;                 pq.push(make_pair(ncost, next));             }         }     } } void bfs(int start){     queue<int> q;     q.push(start);     while (!q.empty()){         int here = q.front();         q.pop();         for (auto n : adj[here]){             int next = n.second;             int cost = n.first;             if (dist[next] == dist[here] + cost){    // here까지 최단거리로 오고 next까지 최단거리로 한번 더 이동할 수 있다면                 q.push(next);                 if (here != start){                     if (!visit[here]) ans++;                     visit[here] = true;            //통행료를 걷을 수 있는 지점                 }             }         }     } } int main(){     setbuf(stdout, NULL);     int T;     scanf("%d", &T);          for (int t = 1; t <= T; t++){         ans = 0;         scanf("%d%d", &N, &M);         adj = vector<vector<pair<int, int> > >(N + 1);         visit = vector<bool>(N + 1, false);         for (int m = 0; m < M; m++){             int u, v, d;             scanf("%d%d%d", &u, &v, &d);             adj[u].push_back(make_pair(d, v));             adj[v].push_back(make_pair(d, u));         }         for (int n = 1; n <= N; n++){             dist = vector<int>(N + 1, INF);             dijkstra(n);             bfs(n);         }         printf("Case #%d\n", t);         printf("%d ", N - ans);         for (int n = 1; n <= N; n++)             if (!visit[n])                 printf("%d ", n);         printf("\n");     }      return 0; } Colored by Color Scripter

cs

3. 캠퍼스와 도로(2)
이 문제때문에 글쓴거다. BFS방식 말고 prev배열에 저장하는 방식을 사용했는데

거리가 갱신될때 prev를 초기화하지 않아서 틀렸다.

어떤정점 V를 갈 수 있는 최단경로가 2개이상 있을 때는 다른경로로 가면 되지만

한개뿐일때는 꼭 그 정점을 지나야 V를 가는데 최단거리가 된다.

따라서 정점 V를 가기위한 최단경로의 정점이 한개뿐일때의 정점들이 답이된다. 
(단, 정점이 시작정점인 경우는 제외해야한다.)

#include <cstdio> #include <vector> #include <algorithm> #include <functional> #include <queue> using namespace std; #define INF 987654321 int N, M; vector<vector<pair<int, int> > > adj; vector<vector<int> > par; vector<bool> visit; void dijkstra(int start){             vector<int> dist(N + 1, INF);     par = vector<vector<int> >(N + 1, vector<int>());     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pq;          dist[start] = 0;     pq.push(make_pair(0, start));     while (!pq.empty()){         int here = pq.top().second;         pq.pop();         for (auto n : adj[here]){             int next = n.second;             int ncost = dist[here] + n.first;             if (dist[next] > ncost){                 dist[next] = ncost;                 pq.push(make_pair(ncost, next));                 par[next].clear();                 par[next].push_back(here);             }             else if (dist[next] == ncost){                 par[next].push_back(here);             }         }     }     for (int next = 1; next <= N; next++){         if (start != next && par[next].size() == 1){        //next까지 도달하는데 최단 경로가 한개(here->next 경로)밖에 없다면                 int must = par[next][0];             if (must != start){                 visit[must] = true;             }         }     } } int main(){     setbuf(stdout, NULL);     int T;     scanf("%d", &T);     for (int t = 1; t <= T; t++){         scanf("%d%d", &N, &M);         adj = vector < vector<pair<int, int> > >(N + 1);         visit = vector<bool>(N + 1, false);              for (int m = 0; m < M; m++){             int u, v, d;             scanf("%d%d%d", &u, &v, &d);             adj[u].push_back(make_pair(d, v));             adj[v].push_back(make_pair(d, u));         }         int ans = 0;         for (int start = 1; start <= N; start++)             dijkstra(start);                  for (int n = 1; n <= N; n++)             if (visit[n])                  ans++;         printf("Case #%d\n", t);         printf("%d ", ans);         for (int n = 1; n <= N; n++)             if (visit[n]) printf("%d ", n);         printf("\n");     }     return 0; } C olored by Color Scripter

cs

4. 개코전쟁, 도로검문

간선을 하나 삭제시켜 최단거리의 값이 최대인 거리를 구하는 문제이다.

핵심 풀이는 지워야 하는 간선은 간선을 삭제하지 않고 최단경로를 만드는 경로의 간선이라는 것이다.

당연하게도 최단경로가 아닌 간선을 지워봤자 최단경로는 변하지 않을 것이다.

또한 최단경로가 여러개있어도 한개의 최단경로만 파악해 놓아도 된다.

어떤 정점까지 가는 최단경로가 여러개 있다면 그 중 한개의 간선을 제거한다 해도 변하지 않거나 

한 개의 최단 경로만 파악해 놓고 삭제한 결과랑 같기 때문이다. 

이 문제를 처음엔 못풀었는데 위의 유도과정을 생각치 못한것 같다. 

#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; #define INF 987654321 int N, M; int par[1001]; vector<pair<int,int>> adj[1001]; void dijkstra1() {     vector<int> dist(N + 1, INF);     priority_queue<pair<int, int>> pq;     fill(par, par + N + 1, -1);     pq.push({ 0,1 });     while (!pq.empty()) {         int here = pq.top().second;         int cost = -pq.top().first;         pq.pop();         for (auto n : adj[here]) {             int next = n.second;             int ncost = n.first + cost;             if (dist[next] > ncost) {                 dist[next] = ncost;                 par[next] = here;                 pq.push({ -ncost,next });             }         }     } } int dijkstra2(int notgo_u, int notgo_v) {     vector<int> dist(N + 1, INF);     priority_queue<pair<int, int>> pq;     pq.push({ 0, 1 });     while (!pq.empty()) {         int here = pq.top().second;         int cost = -pq.top().first;         pq.pop();         for (auto n : adj[here]) {             int next = n.second;             if ((here == notgo_u && next == notgo_v) || (here == notgo_v && next == notgo_u)) continue;             int ncost = n.first + cost;             if (dist[next] > ncost) {                 dist[next] = ncost;                 pq.push({ -ncost,next });             }         }     }     return dist[N]; } int main() {     scanf("%d%d", &N, &M);     for (int m = 0;m < M;m++) {         int u, v, d;         scanf("%d%d%d", &u, &v, &d);         adj[u].push_back({ d,v });         adj[v].push_back({ d,u });     }     dijkstra1();     int ans = 0;     for (int i = N;;i = par[i]) {         ans = max(ans, dijkstra2(par[i], i));         if (par[i] == 1) break;     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

5. The Other Way

이것은 추적은 아니지만 지속적으로 갱신 및 저장하는것이 비슷해서 넣었다.

S에서 E로 가는 경우의 수를 구하는 문제이다.

DP를 이용하는데 먼저 소스를 올리겠다.

#include <cstdio> #include <vector> #include <queue> #include <functional> #include <algorithm> #define INF 1987654321987654321 #define mod 1000000009 using namespace std; int N, M; vector<pair<int, int>> adj[100001]; int dp[100001]; long long dist[100001]; void dijkstra(int start, int end) {     priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;          fill(dist + 1, dist + N + 1, INF);     dist[start] = 0;     dp[start] = 1;     pq.push({ 0,start });     while (!pq.empty()) {         int here = pq.top().second;         long long hdist = pq.top().first;             pq.pop();         if (dist[here] ^ hdist) continue;         for (auto n : adj[here]) {             int next = n.second;             long long cost = (long long)n.first + dist[here];             if (dist[next] > cost) {                 dp[next] = dp[here] % mod;                 dist[next] = cost;                 pq.push({ cost,next });             }             else if (dist[next] == cost) {                 dp[next] += dp[here];                 dp[next] %= mod;             }         }     } } int main() {     int s, e;     scanf("%d%d%d%d", &N, &M,&s,&e);     for (int m = 0;m < M;m++) {         int u, v, d;         scanf("%d%d%d", &u, &v, &d);         adj[u].push_back({ d,v });         adj[v].push_back({ d,u });     }     dijkstra(s,e);     printf("%d\n", dp[e]);     return 0; } Colored by Color Scripter

cs

다익스트라 내부에 있는 if (dist[here] ^ hdist) continue;  이 코드 때문에 애를 먹었다.

(if (dist[here] < hdist) continue; 이렇게 써도 된다.)

바로 반례를 들자면 

4 5 1 4 1 2 1 1 3 4 2 3 1 3 4 4 3 4 6
ans : 1
If none of this sentence {if (dist[here] ^ hdist) continue;}, then : 2

나머지 부분은 충분히 이해가 되기때문에 생략한다.

6. LG CNS 2017 Codemonster E번

정확한 풀이인지는 채점을 하지 못해서 장담하지는 못한다.
(박트리님 블로그를 참고하여 아마 맞는 풀이일듯)

// CNS 그래프는 기존 그래프의 최단경로를 유지하되 edge 가중치들의 합이 가장 작은 그래프이다. // 정점과 방향성 있는 간선들의 정보들이 주어질때 CNS 그래프의 가중치의 합을 구하는 문제다. #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; #define INF (ll)(1e18) int N, M; vector<pair<ll, pair<int, int>>> adj[1111]; ll dist[1111]; vector<int> par[1111]; vector<int> edge[20001]; int cnt = 0; vector<bool> visit; void dijkstra(int start) {     memset(dist, 0x3f, sizeof dist);     priority_queue<pair<ll, int>> pq;     dist[start] = 0;     pq.push({ 0,start });     while (!pq.empty()) {         int here = pq.top().second;         ll cost = -pq.top().first;         pq.pop();         if (dist[here] < cost) continue;         for (auto &n : adj[here]) {             int next = n.second.first;             ll ncost = n.first + dist[here];             if (dist[next] > ncost) {                 dist[next] = ncost;                 par[next].clear();                 par[next].push_back(n.second.second);                 pq.push({ -ncost,next });             }             else if (dist[next] == ncost) {                 par[next].push_back(n.second.second);             }         }     }     for (int n = 1;n <= N;n++) {         if (par[n].empty()) continue;         for (int m = 0;m < par[n].size();++m) {             edge[par[n][m]].push_back(cnt);         }         cnt++;     } } int main() {     scanf("%d%d", &N, &M);     vector<pair<ll, int>> vadj;     for (int m = 0;m < M;m++) {         int u, v, d;         scanf("%d%d%d", &u, &v, &d);         adj[u].push_back({ (ll)d, {v, m} });         vadj.push_back({ (ll)d,m });     }     for (int n = 1;n <= N;n++)          dijkstra(n);          sort(vadj.begin(), vadj.end());     ll ans = 0;     visit.resize(cnt + 1, false);     for (int n = 0;n < vadj.size();++n) {         ll cost = vadj[n].first;         int idx = vadj[n].second;         bool flag = false;         for (int m = 0;m < edge[idx].size();++m) {             //이미 모두 방문했으면 이 간선으로 통하는 최단경로가 다 존재하므로             //이 간선을 추가시킬 필요가 없다.             if (!visit[edge[idx][m]]) flag = true;             }         if (flag) ans += cost;         for (int m = 0;m < edge[idx].size();++m) {             visit[edge[idx][m]] = true;         }     }     printf("%lld\n", ans);     return 0; } Colored by Color Scripter

cs