Eunbi

정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제거해 나갈 것이다. 이때, 특정 정점 s와 t가 비연결이 되는 시점에서 간선 제거를 멈출 것이다. s와 t가 비연결이 되는 시점의 지운 간선의 가중치의 합이 최대가 되게 제거하는 간선의 순서를 조정할 때, 그 최댓값을 구하시오. → 그래프에서 간선을 지울건데, 지운 간선의 총합이 최대이어야하고 간선을 지울때 s, t가 끊어진다면 그때 멈추어야함. → 그럼 비연결이 될 때까지 최대한 많은 간선을 지워야하고, 즉 s-t를 잇는 경로를 제외한 모든 간선들을 지우게 됨. 그리고 추가로 s-t를 잇는 최단 경로(간선의 합이 최소..

이 프로그램에 출연하는 N명의 요리사는 각각 요리 실력 Pi와 인기도 Ci를 갖고 있다. 이 프로그램의 시청률은 그 날 요리 대결을 펼치는 두 요리사의 요리 실력과 인기도에 의해 결정된다. 남규는 총 N-1번의 경기 동안, 경기 순서와 승패를 잘 정해서 시청률의 총합을 최대화 → N명의 요리사가 있으면 N-1번의 경기를 치루고, 각 경기마다 시청률이라는 값을 지니고 있으며 각 경기들의 시청률의 합을 최대화하는 방법을 구해야 한다. N명의 요리사를 노드로 두고 N-1번의 경기를 간선으로 생각한다면 이는 트리의 형태가 되고, 최소(최대) 스패닝 트리를 구하는 문제로 볼 수 있다. → 어떤 경기(i번째 요리사 vs. j번째 요리사)가 이루어져야 최대 시청률합이 나오는지 알 수 있다. 하지만 어떤 순서로 경기를..

잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다. → 전선을 잘라내는데 모두 동일한 비용이 든다. 그리고 전선이 꼬여있지 않으려면 왼쪽 전봇대를 커지는 차례로, 연결된 오른쪽 전봇대의 숫자를 확인했을 때 앞서 나온 전봇대 숫자보다 커야 꼬여있지 않은 상태가 된다. 즉, 연결된 오른쪽 전봇대 숫자를 수열로 보고 이 수열에서 가장 길이가 긴 증가하는 부분수열을 구했을 때 가장 적은 비용으로 전봇대의 전선을 자르는 꼴이 된다. 가장 길이가 긴 증가하는 부분수열의 길이를 구하기 → 부분수열에 있는 원소를 구하는 것이 아닌 길이만 구하면 되는 문제이다. #include #include #include using namespace std; int N, x; vector arr; int ma..

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. → 조건1. 내가 갈 수 있는 섬의 x좌표는 나보다 크거나 같다. 조건2. 조건1을 만족할 때, 내가 갈 수 있는 섬의 y좌표는 나보다 작거나 같다. ==> (입력받을 때 y에 -1를 곱한다면) 조건1. 내가 갈 수 있는 섬의 x좌표는 나보다 크거나 같다. 조건2. 조건1을 만족할 때, 내가 갈 수 있는 섬의 y좌표는 나보다 크거나 같다. x, y 좌표를 오름차순으로 정렬했을 때, 하나씩 탐색하면 x 조건은 자동으로 성립한다. → 따라서 정렬하면 x 좌표값이 필요없게 됨. y 좌표만 보고 y 조건이 성립하는지 판단하는 문제로 변함. 하나씩 탐색을 했을 때 해당 y..