jay153의 PS 일지

https://www.acmicpc.net/problem/18976  코드http://boj.kr/97c257d8f1b74482be14bb8980f3227c Petrozavodsk Programming Camp Summer 2018 Day 3: MIPT Contest K 난이도 : P2 Elapse Time : 15min 문제를 보고 단순화를 해야겠다는 생각이 들었다. 결국 문제를 요약하면 점과 선분들에 의해 몇 개로 나누어져 있는 평면에서 최소비용의 선분을 제거하여 평면이 분리되어 있지 않도록 만들라는 것이었다. 처음에는 분리되어 있는 평면들에 각각 번호를 붙여준 뒤 비용 순으로 선분들을 정렬하고 선분을 기준으로 양쪽에 있는 평면이 같은 평면인지 확인하는 것을 Dsu를 활용해 처리해 줄 생각이었다. 평..

https://atcoder.jp/contests/arc194   Performance Rating : 1900 A수열에서 연속한 2개의 항을 함께 제거할 수 있고 제거한 뒤 수열의 합을 최대로 만드는 문제인데 $dp[i]$를 $A_1$,$\cdots$,$A_i$까지의 숫자들로 만들 수 있는 합의 최댓값이라고 정의하면 $dp[i]=\mathrm{max}(dp[i-1]+A_i,dp[i-2])$라는 식을 세울 수 있다. B가장 큰 원소를 뒤로 보내는 방식으로 버블정렬을 할 때가 최선이라고 생각했다. $x$가 $x$번째로 가기 위해서는 자신보다 뒤에 있는 $x$보다 작은 수들을 앞으로 보내야 하는데 이를 최대한 앞에서 하려면 자신보다 큰 수들을 모두 제자리에 놓고 해야하기 때문이다. 이렇게 정성적으로 생각한 ..