DP 썸네일형 리스트형 백준 2673번 교차하지 않는 원의 현들의 최대집합 http://icpc.me/2673 2673번: 교차하지 않는 원의 현들의 최대집합 평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로 붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서 www.acmicpc.net 풀이 원의 현이라고 하면 되게 복잡해지고 풀기 싫어집니다. 하지만 두 현의 교차 여부만 중요하다는 점을 잘 생각해 보면 현을 수평선상의 구간으로 생각해도 문제가 없다는 것을 알 수 있습니다. 두 현의 교차하려면 각 현을 나타낸 두 구간이 겹치면서 한 구간이 다른 구간에 포함되지 않아야 합니다. 아래 그림은 예제를 구간으로 나타낸 모습입니다. 여기까지 왔으면 DP로 문제를 풀 수 있습니다. .. 더보기 Codeforces Round #672 (Div. 2) A~C1번 풀이 얼마 전 Codeforces Round #672 (Div. 2)에 참가했습니다. 처음으로 문제를 3개나 풀어서 행복했습니다. 그래서 대회 중 풀었던 A번, B번, C1번의 풀이를 써 보려 합니다. A번 - Cubes Sorting 문제 Problem - A - Codeforces codeforces.com 문제 설명 $N$개의 정육면체가 한 줄로 놓여 있을 때, 부피가 큰 순으로 정렬한다고 합니다. 단, 두 인접한 정육면체를 교환하는 작업만 할 수 있습니다. 각 정육면체의 부피가 주어질 때, 정렬을 위해 필요한 최소 교환 횟수가 $\frac{N\times (N-1)}{2}$회 미만이라면 YES, 아니면 NO를 출력하는 문제입니다. 풀이 두 인접한 원소만 교환하여 정렬하는 알고리즘으로는 버블 정렬이 있습니.. 더보기 이전 1 다음
