너와 나의 스토리

문제: 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..

문제: https://www.acmicpc.net/problem/1922 문제 풀이: mst 사용 ㅎㅎ 소스 코드: typedef pair P; priority_queue pq; int n, m,cnt,p[1001],res; int find(int x) { if (p[x] > n >> m; memset(p, ..