3421 수제 버거 장인 [D5]
3503 초보자를 위한 점프대 배치하기 [D5]
4747 사막에서 만난 지니 [D6]
3082 화면 보호기 [D7] https://www.acmicpc.net/problem/3990
1. 1858 모범 택시 드라이버
N개의 도시와 M개의 도로가 있다.
각 도로는 일방통행이며 제한속도 V와 도로의 길이 L이 주어진다.
V가 0인경우에는 이전속도를 유지하며 달린다.
0번도시에서 70의 속도로 출발할 때 D까지 도달하는 최단 시간 경로를 구하는 문제이다.
============================================================================
도로를 이동할 때는 제한속도 V만큼의 속도로 가는것이 가장 최단시간에 갈 수 있는것을 알 수 있다.
각 도시를 도달할때의 속도가 다르고 시간또한 다르기 때문에 정점을 N*V개 놓고 다익스트라를
돌리면 된다.
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 155;
const int MAXM = 505;
#define INF (987654321)
int T, n, m, d;
vector<pair<int, pair<int, int>>> adj[MAXN]; //e, v, l
double dist[MAXN][MAXM];
pair<int,int> par[MAXN][MAXM];
void dijkstra() {
for (int i = 0; i < n; i++) for (int j = 0; j < MAXM; j++) dist[i][j] = INF;
priority_queue<pair<double, pair<int, int>>> pq;
dist[0][70] = 0;
pq.push({ 0,{70, 0} });
while (!pq.empty()) {
double t = -pq.top().first;
int v = pq.top().second.first;
int here = pq.top().second.second;
pq.pop();
if (here == d) return;
for (pair<int, pair<int, int>> x : adj[here]) {
int nxt = x.first;
int limit = x.second.first;
int len = x.second.second;
if (limit == 0) limit = v;
double cost = len / (double)limit;
if (dist[nxt][limit] > t + cost) {
dist[nxt][limit] = t + cost;
pq.push({ -dist[nxt][limit], {limit, nxt} });
par[nxt][limit] = { here, v };
}
}
}
}
int main() {
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
scanf("%d%d%d", &n, &m, &d);
for (int i = 0; i < MAXN; i++) adj[i].clear();
for (int i = 0; i < m; i++) {
int s, e, v, l;
scanf("%d%d%d%d", &s, &e, &v, &l);
adj[s].push_back({ e,{v,l} });
}
dijkstra();
double v = INF;
int st = -1;
for (int i = 1; i < MAXM; i++) {
if (dist[d][i] < v) {
v = dist[d][i];
st = i;
}
}
stack<int> stk;
for (pair<int, int> x = { d, st };; x = par[x.first][x.second]) {
stk.push(x.first);
if (x.first == 0 && x.second == 70) break;
}
printf("#%d ", t);
while (!stk.empty()) printf("%d ", stk.top()), stk.pop();
puts("");
}
return 0;
}
| cs |
2. 3421 수제 버거 장인
N개의 재료가 있고 M개의 궁합이 맞지않는 쌍이 주어진다.
N개의 재료들로 만들 수 있는 조합의 개수를 구하는 문제이다.
============================================================================
처음에는 $O(2^NM)$의 복잡도로 제출했는데 통과가 되긴하였다.
사실 $O(2^N)$풀이가 존재한다.
각각의 재료마다 궁합이 맞지않는 다른 재료들을 bit mask형태로 저장해 놓는다.
$2^N$의 경우를 보며 현재 재료를 넣어도 되는 경우에만 넣으면 된다.
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
int T, n, m, cnt;
int no[20];
void solve(int idx, int info) {
if (idx == n) {
cnt++;
return;
}
if (!(no[idx] & info)) solve(idx + 1, info | (1 << idx));
solve(idx + 1, info);
}
int main() {
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
cnt = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) no[i] = 0;
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
u--; v--;
no[u] |= (1 << v);
no[v] |= (1 << u);
}
solve(0, 0);
printf("#%d %d\n", t, cnt);
}
return 0;
}
| cs |
3. 3503 초보자를 위한 점프대 배치하기
N개의 막대를 재배치하여 두 막대의 최대 높이차가 최소화하는 문제이다.
============================================================================
직관적으로 정렬을 시키고 가우시안 분포처럼 막대를 배치하는것이 최적일거 같은 느낌이든다.
실제로도 답이고 정확한 증명은 좀더 고민을 해봐야 겠다.
doju님의 증명 힌트 :
그 직관적으로 나오는 답에서 간격 상한을 더 줄였을 때 사이클이 생길 수 없음을
증명하는 방향으로 시도해 보세요.
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int T, n, arr[MAXN];
int tmp[MAXN];
int main() {
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
sort(arr, arr + n);
int l = 0, r = n - 1;
for (int i = 0; i < n; i++) {
if (~i & 1) tmp[l++] = arr[i];
else tmp[r--] = arr[i];
}
int ans = abs(tmp[0] - tmp[n - 1]);
for (int i = 0; i < n - 1; i++) ans = max(ans, abs(tmp[i] - tmp[i + 1]));
printf("#%d %d\n", t, ans);
}
return 0;
}
| cs |
4. 4747 사막에서 만난 지니
N개의 수열이 주어졌을 때 각각의 합이 같도록 3가지로 분류하는 방법을 구하는 문제이다.
즉, [1, 4, 2, 3, 2]가 주어진다면 [1, 3], [2, 2], [4]로 분류할 수 있다.
또한 수열의 값들은 균등하게 분포되있다.
============================================================================
N이 사실상 2,000이여서 마땅한 방법을 생각해내기 어렵다.
푸는 방법도 다양한 방법이 존재할것 같은 문제다.
우선 각각의 분류에는 (수열의 합 / 3)만큼이 할당되어야 할 것이다.
나는 각각의 분류를 동시에 채우는 것이 아니라 하나의 분류를 채운 후에
나머지 분류들을 채우는 방식으로 구현하였다.
채울 때에는 큰 수부터 작은수를 넣고 채우는것이 불가능하면 back-tracking하여
다시 탐색을 진행한다.
시간 복잡도는 $O(3^N)$이다. 수열의 값이 균등하여 최악의 시간내에는 답이 나온다.
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int T, n;
int arr[MAXN];
bool visit[MAXN];
int s;
vector<int> ans[3];
bool f;
void solve(int xdi, int idx, int sum) {
if (xdi == 2) {
f = true;
return;
}
if (sum == s) {
solve(xdi + 1, n - 1, 0);
return;
}
if (idx < 0) return;
if (visit[idx]) {
solve(xdi, idx - 1, sum);
return;
}
if (f) return;
if (sum + arr[idx] <= s) {
visit[idx] = true;
ans[xdi].push_back(arr[idx]);
solve(xdi, idx - 1, sum + arr[idx]);
if (f) return;
ans[xdi].pop_back();
visit[idx] = false;
}
if (f) return;
solve(xdi, idx - 1, sum);
}
int main() {
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
memset(visit, 0, sizeof visit);
f = false;
scanf("%d", &n);
s = 0;
for (int i = 0; i < 3; i++) ans[i].clear();
for (int i = 0; i < n; i++) scanf("%d", &arr[i]), s += arr[i];
s /= 3;
solve(0, n - 1, 0);
printf("#%d\n", t);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < ans[i].size(); j++) printf("%d ", ans[i][j]);
puts("");
}
for (int i = 0; i < n; i++) if (!visit[i]) printf("%d ", arr[i]);
puts("");
}
return 0;
}
| cs |
5. 3082 화면 보호기
풀지 못했다. 좀더 고민해봐야겠다 ㅠㅠ
