문제은행 & BOJ 2673 교차하지 않는 원의 현들의 최대집합(C++)

1769 : 교차하지 않는 원의 현들의 최대집합

제한시간: 1000 ms    메모리제한: 0 MB
해결횟수: 14 회    시도횟수: 62 회   

평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서로 교차하지 않는 것들을 최대한 많이 찾아서 그 개수를 출력하는 프로그램을 작성하라. 
단, 1≤N≤50이고, 주어진 각 점은 많아야 한 현의 끝점이 될 수 있다.

 

첫 번째줄은 주어지는 현의 개수 N이고, 다음의 N줄은 각 현의 양끝점의 번호가 주어진다.

구한 현의 개수를 출력한다.

[Copy] 5 97 31 1 45 27 5 11 65 43 72

[Copy] 3

[도움말 접기]

예로 주어진 입력자료를 그림으로 그리면 아래와 같다.

주어진 다섯 개의 현중에서 서로 교차하지 않는 현들을 최대로 구하면(27,5),(97,31),(43,72)로 세 개가 된다.

출처 : KOI 전국 1996 고2

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

/**************************************************************     Problem: 1769     User: a132034     Language: C++     Result: Success     Time:1 ms     Memory:1188 kb ****************************************************************/     #include    <cstdio> #define max(x,y) ((x)>(y)?(x):(y)) #pragma warning (disable:4996)    int P[111][111]; int D[111][111]; int main() {     int N, s, e;     scanf("%d", &N);     for (int i = 1; i <= N; ++i)     {         scanf("%d%d", &s, &e);         P[s][e] = P[e][s] = 1;     }     for (int i = 100; i > 0; --i)     {         for (int j = i + 1; j <= 100; ++j)         {             for (int k = i; k < j; ++k)                 D[i][j] = max(D[i][j], D[i][k] + D[k + 1][j - 1] + P[i][j]);         }     }     printf("%d", D[1][100]);     return 0; }

다이나믹 프로그래밍. 

원으로 보면 상당히 어려우나 0부터 100까지의 직선이라고 생각한다면 문제가 조금 더 단순해진다. 

D[i][j]를 i와 j점 사이의 최대의 교차하지 않는 원의 현 집합이라고 생각한다면 

분명 현끼리 수직선 상에서 겹치지 않는다면 교차하지 않게 될 것이다. 

예를들어 1 - 100인 현과 2 - 30인 현 그리고 50 - 60인 현은 교차하지 않는다. 

하지만 2 - 40 인 현과 30 - 50인 현은 수직선 상에서 겹치므로 교차하게 될 것이다. 

실제로 그려본다면 쉽게 이해할 수 있다. 

이러한 조건을 이용해서 점화식으로 나타내 보면

이는 D[i][k]까지의 최대집합 + D[k+1][j-1]까지의 최대집합 + i,j를 잇는 현까지. 라고 할 수 있다. 

이때 k는 i~j사이의 임의의 값이다. 

-> 구하려는 값은 D[1][100]이 될 것이고 이는 

D[1][1] + D[2][99] ~ D[1][99] + D[99][99] + 1과 100을 잇는 현(없다면 0) 이 될 것이다. 

(문제의 조건에서 한 점은 많아야 한 현의 점이 될 수 있다고 하였으므로 D[x][x] = 0이 될 것이다.) 

추가로 

다이나믹 프로그래밍에서 중요한 것은 먼저 계산한 것을 가져다 사용하는 것인데 

먼저 계산한 것을 사용하려면 가장 작은 집합부터 사용해야 한다. 이를 위해 

for loop의 가장 처음 index인 i가 1부터 시작이 아닌 100부터 1씩 줄어들게 하였다. 

이렇게 하면 

D[99][100] => D[98][99] => D[98][100] .... 순서로 작은 것 부터 계산하기 때문에 이전에 계산된 값을 사용할 수있게 된다.