너와 나의 스토리

문제: https://www.acmicpc.net/problem/4013 문제 풀이: https://hororolol.tistory.com/116랑 거의 비슷한 문제 다른점은 현재 위치에 레스토랑이 있다고 바로 break하는 것이 아니라 최대값을 찾을 때까지 연산함 소스 코드: int n, m, cost[500001], p[500001], scc[500001],dist[500001], res; bool visit[500001], rest[500001]; vector adj, adj2, scc_adj; stack st; void dfs(int v) { visit[v] = true; for (int i : adj[v]) { if (visit[i]) continue; dfs(i); } st.push(v); }..

문제: https://www.acmicpc.net/problem/2152 문제 풀이: scc로 묶어서 간선 만듦 시작점과 끝점의 scc가 같으면 그 scc의 개수 출력 다르면 bfs돌려서 출력 소스 코드: int n, m,s,k, p[10001],scc[10001],dist[10001]; bool visit[10001]; vector adj,adj2,scc_adj; stack st; void dfs(int v) { visit[v] = true; for (int i : adj[v]) { if (visit[i]) continue; dfs(i); } st.push(v); } void rdfs(int v, int t) { visit[v] = true; p[v] = t; scc[t]++; for (int i : ..

문제: https://www.acmicpc.net/problem/3977 문제 풀이: scc를 구하는데 각 점들의 scc번호를 p배열에 저장함 scc를 구하는 dfs 중 a->b를 가리켰는데 b가 이미 visit이라면 case1: b가 다른 scc인 경우 (p[a]!=p[b]) degree[a]++ case2: b가 같은 scc인 경우는 그냥 패스 이렇게 했을 때 degree가 0인 scc가 한 개이면 그 scc를 정렬해서 출력하면 되고 두 개 이상이면 "Confused" 출력 소스 코드: int tc, n, m,p[100001],degree[100001]; bool visit[100001]; vector adj,adj2; stack st; vector scc; void dfs(int v,bool t) ..

문제: https://www.acmicpc.net/problem/17074 문제 풀이: 오름차순인 구간을 나눔 ex) 123845인 경우 각각 0~3, 4~5번째 값들은 오름차순으로 정렬되어 있다. 그럼 경계에 있는 3, 4번 값이 뺄 수 있는 값의 후보이다 만약 3번을 뺐을 때, 4번을 뺐을 때 둘 다 정렬된 값이면 답은 2 즉, 답의 최대값은 2이다. 구간이 3개 이상이 나오면 어떤 값을 빼도 정렬될 수 없으므로 답은 0 case1: 왼쪽 구간이 한개만 존재하는 경우 case1-1: 오른쪽 구간도 한개만 존재하는 경우 -> 두 개다 뺄 수 있으므로 답은 2 case1-2: 오른쪽 구간은 여러개인 경우 -> 오른쪽 경계 뺐을 때 오름차순이면 답은 2 -> 아니면 왼쪽 값만 뺄 수 있으므로 답은 1 ca..

문제: https://www.acmicpc.net/problem/12789 소스코드: int n; queue q1; stack st; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 0; i > q; q1.push(q); } int order = 1; while (!q1.empty()) { int cur = q1.front(); if (cur == order) { order++; q1.pop(); } else{ if (!st.empty()&&st.top() == order) { st.pop(); order++; } else { st.push..

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