Eunbi

터보소트는 1부터 N까지 총 N개의 수가 섞여있을 때만 사용할 수 있으며, 다음과 같이 N단계로 이루어져 있다. 첫 번째 단계에서 숫자 1의 위치를 찾는다. 그 다음 바로 앞의 숫자와 위치를 바꾸어가면서, 1이 제일 앞에 오게 바꾼다. 두 번째 단계에서는 숫자 N의 위치를 찾는다. 그 다음 바로 뒤의 숫자와 위치를 바꾸어가면서, N이 제일 마지막에 오게 바꾼다. 세 번째 단계는 숫자 2의 위치를 찾은 후에, 바로 앞의 숫자와 위치를 바꾸어가면서, 두 번째 위치에 오게 바꾼다. 네 번째 단계는 숫자 N-1의 위치를 찾은 다음에, 바로 뒤의 숫자와 위치를 바꾸면서, 뒤에서 2번째 위치에 오게 바꾼다. 다섯 번째 단계도 위와 같은 식으로 하면 되고 이를 N번 반복하는 것이다. 정리하면, 홀수번째 단계이면, 아..

정점 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..