너와 나의 스토리

문제: https://www.acmicpc.net/problem/12788 소스 코드: int n,team,t,arr[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n>>team>>t; team *= t; for (int i = 0; i > arr[i]; } sort(arr, arr + n,greater()); int tmp=0; for (int i = 0; i = team) { cout

문제: https://www.acmicpc.net/problem/12782 문제 풀이: index 01234567 a: 00110100 b: 10010111 가 주어졌을 때, index 0, 2, 6, 7가 다르며 각각의 b의 값은 1 0 1 1이다. (->one=3, zero=1) 즉, a와 다른 지점이 각각 0과 1이면 서로 바꿔주면된다. 1의 개수와 0의 개수 중 작은 값만큼 swap해주면 됨 -> min(one,zero) 그리고 남은 것들은 0은 1로, 1은 0으로 바꿔주면 됨 -> one+two-min(one,zero)*2 소스코드: int tc; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> tc;..

문제: https://www.acmicpc.net/problem/4386 문제 풀이: mst를 사용한 문제 각 점들의 (x,y)값을 입력 받아 벡터에 저장하고 한 별에서 다른 별들로 갈 수 있는 모든 경로의 길이를 priority_queue에 저장 가장 짧은 길이를 가진 두 별을 팝해와서 이미 연결된 노드는 패스하고 아니면 연결해주고 그 길이를 res에 더해줌 최소만 연결하면 n-1개의 다리(?)가 생기므로 다 연결했으면 바로 break해주면 됨 소스 코드: typedef pair P; int n,p[101],cnt; double res; bool visit[101]; vector adj; priority_queue pq; int find(int x) { if (p[x] < 0) return x; ret..

문제: https://www.acmicpc.net/problem/4196 문제풀이: dfs돌려서 stack에 정점들 쌓아주고 stack에서 정점 빼주면서 다시 dfs 돌리면서 visit해줌 stack에서 뺀 정점이 이미 visit되어 있으면 다시 빼고 아니면 res++해주고 dfs 돌림 * https://hororolol.tistory.com/94 > tc; while (tc--) { cin >> n >> m; memset(visit, false, sizeof(visit)); int res = 0; adj.clear(); adj.resize(n + 1); for (int i = 0; i > q >> w; adj[q].push_back(w); } for (i..

문제: https://www.acmicpc.net/problem/17209 문제 풀이: 현재 보는 사람이 새내기라면 그가 지목한 사람들은 헌내기 현재 보는 사람이 헌내기라면 그가 지목한 사람들은 새내기 즉, 항상 반대 이므로 두가지 경우를 다 돌려줄 필요가 없음 dfs를 이용하여 한 사람을 새내기(새내기=1)라고 두고 그가 지목한 사람은 헌내기(헌내기++) 그 헌내기가 지목한 사람은 새내기(새내기++) 해줘서 max(새내기,헌내기)를 결과 값에 더해준다. 소스 코드: int n,res,people[2]; bool visit[2001]; vector adj; void func(int cur,bool old) { if (visit[cur]) return; visit[cur] = true; for (int i..

문제: https://www.acmicpc.net/problem/13911 문제 풀이: 맥도날드가 있는 곳, 스타벅스가 있는 곳에서 각각 시작해서 다익스트라 돌림 각 정점을 입력 받을 때 pq에 (0,시작정점)으로 넣어넣고 시작하면 한번에 돌릴 수 있음 소스 코드: typedef pair P; int n, m, macs, stars, x, y, dist[2][10001],res=inf; bool visit[2][10001]; vector adj; typedef priority_queue Prior; Prior tmp,tmp2; void di(int cnt,Prior pq) { while (!pq.empty()) { int cur; do { cur = pq.top().second; pq.pop(); } w..

문제: https://www.acmicpc.net/problem/6543 문제 설명: bottom(G) 어떤 정점에서 출발하여 갈 수 있는 모든 정점에서 돌아 올 수 있는 정점들의 집합 ex) 5 5 1 2 2 3 3 1 3 4 4 5 1->2->3->1로 1,2,3이 bottom(G) 속할 것 같아 보이지만 3->4->5로 가고 4나 5에서 1,2,3으로 올 수 없으므로 bottom(G)에 속하지 않음 5는 출발한 정점이 없으므로 bottom(G)에 속함 문제 풀이: 알고리즘 - scc 1. dfs 돌려서 정점 stack에 쌓기 2. scc를 저장하는데 현재까지 저장된 res(scc)의 크기가 t라고 했을 때, 지금 rdfs를 돌려서 얻은 scc는 res[t]이후에 쌓이게 된다 그러므로 한 번 scc ..

문제: https://www.acmicpc.net/problem/1890 문제풀이: "경로의 개수는 2^63-1보다 작거나 같다." -> long long "메모리 제한: 128 MB" -> DP 이미 갔던 길 다시 안가고 그 지점에서 갈 수 있는 경우의 수+1 해주면 됨 * 함수 리턴 타입 확인 잘하자.... int func()해서 계속 틀림 ㅠㅅㅠ 소스코드: int n, arr[100][100]; long long dp[100][100]; long long func(int x, int y) { if (x == n - 1 && y == n - 1) return 1; if (x >= n || y >= n) return 0; long long& ret = dp[x][y]; if (ret != -1) ret..