https://www.acmicpc.net/problem/5542 5542번: JOI 국가의 행사 예제 1. 3에서 4로 가는 경우는 3-5-4로 이동하면 가장 가까운 축제가 6번이고 거리는 7이다. 이 값이 최대이고, 5에서 2로 가는 경우는 5-3-2, 5-4-2 모두 1번 축제와 거리 5가 되므로 이 값을 출력한다. www.acmicpc.net 우선 축제로부터 각 정점까지 최단거리를 저장해 두고, 해당 값을 기반으로 각 간선들을 축제와 가장 먼 순으로 정렬을 한 뒤, 해당 순서로 간선을 그래프에 붙여 나가면서 유니온 파인드를 통해 같은 그룹의 정점은 묶어 나아간다. 같은 그룹으로 묶어 나아가다가 같은 그룹 내에 출발지와 도착점인 사람이 발견되면, 해당 사람의 축제로부터 가장 먼 길이는 방금 붙여지는..

https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 버블 소트가 언제 끝나는지 외부 반복의 횟수를 확인하는 문제이다. 우선 버블 소트는 내부 반복문이 수행될 때마다 앞, 뒤 숫자를 비교 후 앞에 있는 숫자가 바로 뒤 숫자보다 크면 자리를 바꾸는데, 자리를 바꾸며 앞으로 옮겨지는것은 내부 반복문 한번 수행에 대해 각 숫자당 최대 한 번이다. 즉, 한 번의 내부반복에서 앞으로 옮겨진 것은 또 앞으로 옮겨지지 않는다. 또한 자신보..

https://www.acmicpc.net/problem/8872 8872번: 빌라봉 첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. N: 빌라봉의 개수 M: 이미 존재하는 길들의 개수 L: 뱀이 새로 지어진 길을 통행하는데 걸리는 시간 (일 단위). A, B, www.acmicpc.net 가장 지름이 큰 트리의 중점에, 나머지 트리의 중점을 길이 L인 간선을 붙여 연결을 해야지, 임의 두 정점 사이를 오가는데 최대 시간이 최소가 된다. 그렇게 되면 최종적으로 연결된 트리에서 두 정점 사이를 오가는데 최대 시간이 될 수 있는 경우는 다음과 같이 3가지이다. 1. 가장 큰 트리의 지름 2. 가장 큰 트리의 반지름 + 두 번째로 큰 트리의 반지름 + L..

https://www.acmicpc.net/problem/1114 1114번: 통나무 자르기 첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출 www.acmicpc.net 통나무의 가장 큰 길이가 특정 값 이하로 만들 수 있는지 확인하는 이분 탐색 (매개 변수 탐색)을 이용해서 문제를 해결했다. 코드 #include #include #include using namespace std; int l, k, c; vector point; //통나무의 최대 길이가 max_len 이하가 되도록 만들 수 있는지 확인 bool check(int max_len) { int ..

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net cache에 cache[start][end] = "start행렬부터 end행렬까지 곱셈 연산 횟수의 최솟값"을 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n; vector matrix; int cache[505][505]; void pre() { for (int..

https://www.acmicpc.net/problem/15758 15758번: Milking Order Here, Farmer John has four cows and should milk cow 1 before cow 2 and cow 2 before cow 3 (the first observation), cow 4 before cow 2 (the second observation), and cow 3 before cow 4 and cow 4 before cow 1 (the third observation). The first two observation www.acmicpc.net 최대 어떠한 규칙까지 지킬 수 있는지 이분탐색을 통해 확인했고, 규칙이 지켜지는지 여부는 위상정렬로 순서가 만들어지는..