devbelly

문제 https://www.acmicpc.net/problem/20649 알고리즘 DP, Sorting 풀이 x, y 좌표가 모두 다른 소들의 좌표가 주어졌을 때, 각 소들의 잘못 점수(?)를 구하는 문제입니다. 문제를 관찰하면 동쪽으로 이동하는 소들 $A$는 북쪽으로 이동하는 소들 $B$중에서 $A$보다 오른쪽에 있으면서 아래 있는 소들에게 막히는지 안 막히는지 확인해야 하고 반대로 $B$는 $B$보다 왼쪽에 있으면서 위에 있는 소들에게 막히는지 안 막히는지 확인해야 합니다. 그래프가 DAG의 형태를 띠는 것에서 DP를 착안합시다. 이차원 포문을 통해 모든 소들의 쌍을 검사하며 각 소들의 관계를 따져보도록 합시다. 하지만 소들을 정렬하지 않은 채 무작정 이차원 포문을 통해 각 소들의 관계를 따지게 되면..

문제 www.acmicpc.net/problem/18879 알고리즘 sorting 풀이 2차원 공간에 여러 particle들이 주어졌을 때, 상호작용 후 최소한의 particle의 수를 묻고 있습니다. 상호작용의 조건은 $x1\leq x2,\, y1\leq y2$ 을 만족해야합니다. 만약 두 좌표가 있을 때, 상호작용해서 없애야하는 좌표는 상대적으로 오른쪽 위에있는 좌표입니다. 왼쪽 아래 좌표는 후에 다른 좌표들을 더욱 없앨 수 있기 때문입니다. 주어진 좌표들을 정렬한 후, y좌표를 담을 벡터를 만듭니다. 이는 지금까지 살아있는 y좌표들의 그룹입니다. 좌표를 정렬했으므로 좌표벡터의 $i$번쨰 원소는 이전의 모든 좌표들과 상호작용할 첫번째 조건이 충족되었습니다($x1\leq x2$). y좌표만 모아놓은 벡..

문제 www.acmicpc.net/problem/18878 알고리즘 정렬 풀이 $i$번째 소부터 자신의 기호식품의 순위에 따라 가져 갈 때, 각 $i$번째 소마다 몇 개의 시리얼을 나누어 줄 수 있는지 묻는 문제입니다. 문제를 나이브하게 접근하면 처음부터 기호식품을 확인하며 나누어 주면 됩니다. 즉 1번째 소 뒤에 있는 $N-1$마리의 소들에 대해서 나누어주고, 2번째 소 뒤에 있는 $N-2$마리의 소들에 대해 나누어주는 식입니다. 이와 같이 시뮬레이션하면 요구하는 시간 복잡도는 $O(N^2)$ 이므로 시간 초과를 받게 됩니다. 뒤에 서있는 소부터 계산해보도록 합시다. 만약 $k$번째 소 이후에 몇마리가 가져갈 수 있는지를 다 계산을 하였다면 $k-1$번째 소는 이전의 상황과는 관계없이 무조건 자신이 가..