너와 나의 스토리

문제: https://www.acmicpc.net/problem/12763 문제 풀이: dfs로 풀었다 dist[n]에 pair로 시간이랑 금액 저장 현재 가는 정점이 원래 저장된 값(다른 루트로 온 결과 값)보다 시간이랑 금액 둘 다 손해면 안 가고 둘 중 하나라도 이득이면 감 만약 제한된 금액이나 시간이 이미 지나게 되면 안감 소스 코드: typedef pair P; int n,m, time, money,res; vector dist; vector adj; void dfs(int cur) { if (cur == n) { res = min(res, dist[cur].second); return; } for (auto &i : adj[cur]) { if (dist[i.first].first money) ..

문제: https://www.acmicpc.net/problem/14618 문제풀이: 1. 진서집에서 시작해서 다익스트라 돌리기 (양방향) 2. 진서가 가장 빨리 갈 수 있는 집 찾기 B집부터 비교해서 갱신해주고 그 후, A집 비교해줘서 B집이랑 같은 거리이면 A 출력하기 소스코드: #define inf 987654321 using namespace std; typedef pair P; int n, m, jinsu, k,dist[5001]; bool visit[5001]; vector a, b; vector adj; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m;..

문제: https://www.acmicpc.net/problem/15787 문제풀이: 승객 태우기 v[w] = v[w] | (1 w >> e; v[w] = v[w] | (1 > w >> e; v[w] = v[w] &~ (1 > w; v[w] = v[w] w; v[w] = v[w] >> 1; v[w] = v[w] & ~1; } } for (int i = 1; i

문제: https://www.acmicpc.net/problem/15790 문제 풀이: 활의 길이를 기준으로 이분 탐색 (mid=활의 길이) 어떤 홈을 기준으로 시작해서 다음 홈까지의 길이가 mid 이상이면 그 곳을 절단하고, 또, 그 곳부터 길이가 mid 이상인 홈을 만나면 절단. 3겹으로 만든다고 하면, 맨 처음에 시작 점은 이미 골라져 있으므로 2개를 더 찾아 자르고, 마지막 점에서 처음 절단한 곳까지의 길이 또한 mid 이상이면 활의 길이는 mid로 만들 수 있다 주의할 점은, 시작하는 점이 항상 맨 처음 홈이 아닐 수도 있으므로 모든 홈을 처음 홈으로 설정하고 작업 해준다. * 헤헷 남들은 8~40ms 걸리는데 난 104ms나 걸리넹 ㅎㅎ 소스 코드: int n, m, k; vector v; b..

문제: https://www.acmicpc.net/problem/15783 문제 풀이: 1. dfs를 돌려서 스택에 정점들을 넣는다 2. 스택을 pop하면서 그 정점을 시작으로 dfs 돌림 -> visit하면서 이미 다른 정점을 시작으로 방문한 점들은 그냥 pop만 해주고 방문 안한 것들만 cnt++해줌 소스 코드: int n, m,cnt; bool visit[100001]; vector adj; stack st; void dfs(int v,bool t) { if (visit[v]) return; visit[v] = true; for (int i : adj[v]) { dfs(i,t); } if(t) st.push(v); } int main() { ios::sync_with_stdio(false); cin..

문제: https://www.acmicpc.net/problem/15789 문제 풀이: 동맹 왕국들 입력 받을 때마다 merge해주고 cnt[root]=(node 개수) 업데이트 해주기 각 동맹 왕국들의 루트와 동맹 왕국들의 수를 priority_queue에 저장 동맹 기회만큼 merge하는데 자기 자신의 그룹이거나 한솔 왕국 그룹과는 동맹 맺지 않고 그냥 pop 소스 코드: typedef pair P; int n, m,p[100001],cnt[100001]; bool visit[100001]; vector v; priority_queue res; int find(int x) { if (p[x] < 0) return x; return p[x] = find(p[x]); } bool merge(int a, ..

문제: https://www.acmicpc.net/problem/10282 문제 풀이: "단방향"으로 감염됨! a,b,s이면 b->a 감염시키고 a->b 감염 못 시킴 처음 감염된 컴퓨터 기준으로 다익스트라 돌림 그리고 1~N까지 포문 돌리면서 dist[i]!=inf (감염되지 않지 않았다면) cnt++; dist 중에 가장 큰 수가 감염되기까지 걸리는 시간이다. 소스 코드: typedef pair P; vector v; int tc, dist[10001], n, m, k; bool visit[10001]; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> tc; while (t..

문제: https://www.acmicpc.net/problem/1774 문제풀이: 거리를 모두 구해서 priority_queue에 넣음 mst 사용 주의1. double을 사용해야 한다. while문에서 cost를 int형으로 선언한걸 못 찾아서 계속 맞왜틀.... ㅠㅠ 하다가 겨우겨우 맞음 주의2. 미리 연결된 통로들이 항상 mst로 연결되었음을 보장할 수 없다. 즉, while문에서 if(cnt==n-m) break; 이런식으로 풀면 틀림 priority_queue 사용하는 것보다 vector에 거리 차 다 넣어 놓고 sorting 해서 풀면 시간이 절반으로 줄어든다. sort(pq.begin(), pq.end()); for(int i=0;i> n >> m; memset(p, -1, sizeof(p..