와이유스토리

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 재귀 DP #include #include #include #define MAXN 100000 #define INF 1000000000 using namespace std; int n, s, w[16][16], dp[16][MAXN]; int tsp(int u, int v) { if (v == (1 > w[i][j]; } } cout

https://www.acmicpc.net/problem/11657 11657번: 타임머신첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net가중치 음수#include #include #define MAX 501using namespace std;int INF = 1000000000;int n, m, a, b, c;long long dp[MAX];vector v;vector> adj[MAX];int main() { ios_base::sync_with_stdio(0); cin.ti..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 모든 정점에서 최단 경로 찾음 O(N^3) 구현 간단 #include #include #define INF 999999999 #define MAX 501 using namespace std; int n, m, g[MAX][MAX]; int main(void) { cin >> n >> m; for (int i = 1; i > e >> w; if (g[s][e] > w) g[s][e] = w; // ..

https://www.acmicpc.net/problem/1753 시작 정점 하나로부터 최단 경로 찾음 #include #include #include #include #define MAX 20001 #define INF 1e18 using namespace std; bool p; long long a, b, c, cnt, v, e, k; long long dist[MAX]; vector vec[MAX]; priority_queue pq; int main(void) { scanf("%d %d", &v, &e); scanf("%d", &k); for (int i = 0; i < e; i++) { scanf("%d %d %d", &a, &b, &c); vec[a].push_back({ b,c }); } fi..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #include #include #define size 50001 using namespace std; vector graph[size]; int level[size]; int dp[size][30]; // log2(50001) int visited[size]; int n; void dfs(int v, int depth) { visited[v] = 1; level[v] = depth; for..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net #include using namespace std; int n, k; long long ans; int num[10001]; void binarySearch(long long s, long long e) { while (s = n) { // n개 이상 포함할 때 ans = max(ans, m); s = m + 1; } else e = m - 1; } } int mai..

https://www.acmicpc.net/problem/1517 #include using namespace std; int num[500000]; int tempArr[500000]; long long ans; /// 최대 100000C2 void mergeSort(int s, int e) { if (s >= e) return; int m = (s + e) / 2; mergeSort(s, m); mergeSort(m + 1, e); int l = s, cur = s, r = m + 1; while ((l

※ 문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net ※ 풀이 1) 상어와 물고기의 x좌표, y좌표, 방향을 저장할 구조체를 선언하고, 물고기 번호를 저장할 공간 배열, 그리고 물고기 번호별로 x좌표, y좌표, 방향을 저장할 물고기 배열을 따로 선언했다. 그 이유는 물고기를 작은 번호 순대로 이동시켜야 하는데, 공간 배열에 물고기 번호를 저장하면 좌표를 이용해 물고기 번호는 찾을 수 있으나, 물고기 번호를 이용해 물고기 좌..