[BOJ 2673] 교차하지 않는 원의 현들의 최대집합

 DP 문제가 익숙하지는 않아, 이런 문제를 접할 때마다 어렵게 느끼고는 하는데, 처음에 해당 문제를 보고 작성했던 코드가 굉장히 길었던 데에 반해서 매우 짧은 코드로 해결이 가능하기에 해당 코드를 작성해보았습니다. 언어는 Java를 이용했습니다. 아래쪽은 문제의 링크입니다.

https://www.acmicpc.net/problem/2673

 

문    제

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

입    력

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

출    력

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

힌    트

 아래쪽의 코드가 해당 문제에 대해 작성해 본 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;


public class NotCrossChord {

	public static int maxNum = 100;																		// 주어진 점들 중 가장 큰 수
	public static int N = 0;																					// 주어지는 현의 개수
	public static int chord[][] = new int[maxNum + 1][maxNum + 1];							// 원의 현 [시작점][끝점] : 이어진 경우 1, 아닌 경우 0
	public static int maxNotCrossChord[][] = new int[maxNum + 1][maxNum + 1];	 	// 교차하지 않는 최대 현의 개수[시작점][끝점]
	
	public static void main( String[] args ) throws Exception {
		// -- Input Start.
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		N = Integer.parseInt( br.readLine() );
		
		StringTokenizer st = null;
		int start = 0;
		int end = 0;
		for ( int i = 0 ; i < N ; i++ ){
			st = new StringTokenizer( br.readLine() );
			start = Integer.parseInt( st.nextToken() );
			end = Integer.parseInt( st.nextToken() );
			
			chord[end][start] = chord[start][end] = 1;			// 시작점이나 끝점이 반대여도 모두 현이 이어진 것으로 판단
		}
		// -- Input Complete.
		
		// -- Logic Start.
		// 원형으로 생각하지 말고 1 ~ 100까지 있는 x축을 생각, 99 - 100을 잇는 선부터 차근차근 생각하여 안쪽 범위의 최대 현 개수를 구한다.
		for ( int i = maxNum ; i > 0 ; i-- ){						// i 는 시작점
			
			for ( int j = i + 1 ; j <= maxNum ; j++ ){			// j 는 끝점
				
				for ( int k = i ; k < j ; k++ ){						// k 는 시작점부터 끝점까지
					
					// i - j 를 잇는 현과 교차하지 않는 최대의 현 개수 = 시작점 i 부터 k지점까지의 교차하지 않는 최대 현 개수
					//																					+ k+1지점부터 끝점 j까지의 교차하지 않는 최대 현 개수
					//																											+ 자신(i-j 현이 있을 경우 1, 아니면 0)
					maxNotCrossChord[i][j] = Math.max( maxNotCrossChord[i][j], maxNotCrossChord[i][k] + maxNotCrossChord[k+1][j-1] + chord[i][j] );
					// 만일 이전에 탐색했던 값이 더 크면 그 값을 최대값으로 둔다.
				}
				
			}
		}
		// -- Logic End.
		// -- Write Result.
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );
		bw.write( String.valueOf( maxNotCrossChord[1][100] ) );
		bw.flush();
		bw.close();
	}

}

 보시면 사실 코드가 한 눈에 잘 들어오지는 않습니다. 일단 해당 코드를 이해하기 위해서는 컨셉을 명확하게 이해해야 합니다. 일단 해당 문제를 이해하기에 앞서서, 만약 1과 100을 잇는 선분이 있을 경우, 해당 현과 교차하지 않는 최대의 갯수는 2 - 99 까지의 숫자들로 이루어진 현들 중 교차하지 않는 최대의 갯수 + 자기자신 1개 가 됩니다.

 해당 컨셉은 원으로 이해하는 편보다, x축과 같은 직선 위에 1부터 100까지의 숫자를 놓고 생각하는 편이 이해하기 편합니다.

 만약 이 설명이 이해하기 힘드시다면, 1에서 100까지의 숫자가 차례대로 써있는 원을 두고 마지막의 100에서 1로 이어지는 부분을 잘라, 평평하게 편다고 생각해봅시다. 그리고 사이에 이어지는 선분(현)들은 길이가 늘어나더라도 그대로 이어져 있다고 생각해보면, 위의 말이 무슨 말인지 바로 이해하실 수 있을 것이라고 생각합니다.

 그러면 이렇게 원을 잘라서 펴 냈을 경우, 과연 어떤 경우가 선끼리 겹치지 않을까 생각해보면, 문제의 해결에 좀 더 다가설 수 있습니다. 결국 다른 선분과 겹치지 않는 경우는, 다른 선분을 포함하거나, 다른 선분에 포함될 때 뿐이라는 것을 알 수 있죠. 이를 그림으로 표현해보면 아래와 같습니다.

1	2	3	4	5	6                         7

 그림을 표로 그렸더니, 지저분 하네요ㅠㅠ

 아무튼 위의 숫자들을 각각 원 위의 점들이라고 생각해보면 1 - 7 까지 이어져있는 선분은 2 - 4 를 잇는 선분을 포함하고, 실제로 원이 되었을 경우에도 교차하지 않습니다. 2 - 4 를 잇는 선분 입장에서 생각하면 자신을 포함하는 선분과는 겹치지 않습니다. 반면 2 - 4를 잇는 선분과 3 - 5를 잇는 선분은 어떠한 포함관계도 갖고 있지 않습니다. 실제로 원 위에서 그려보면 두 선분은 교차함을 알 수 있죠. 설명이 조잡하지만 이해에 조금 도움이 되셨으면 좋겠습니다.

 그러면 이렇게 이해한 컨셉을 토대로 코드를 작성해야 합니다. 단순히 포함관계만 가지고 생각하려면 이해하기 어려울 수도 있지만, 맨 처음에 제가 말씀드린 대로, 1과 100을 먼저 생각해보면 직선상에서 이어보면 가장 긴 선이기 때문에 모든 선분을 포함하게 됩니다.

 여기서 좀 더 정확한 점화식을 세워보기 위해, 일단 교차하지 않는 최대의 현의 개수를,  만약 A 지점부터 B 지점까지 잇는 선분이 있을 경우, A - B 지점까지 잇는 선분과 교차하지 않는 현의 최대 개수를 maxNotCrossChord[A][B] 라고 두고, 생각해 봅시다. 위에서 설명드렸듯이, A - B 를 잇는 선분과 교차하지 않는 최대의 현의 개수는 포함관계에 있는 선분들 + 자기 자신입니다.

 이를 토대로 특정 A 지점과 B 지점 사이의 선분 위에 있는 임의의 지점 C 를 기준으로 점화식을 세워보면, 아래와 같습니다.

maxNotCrossChord[A][B] = maxNotCrossChord[A][C] + maxNotCrossChord[C+1][B - 1]
                                                   + ( A와 B지점을 잇는 선분이 존재할 경우 1, 아니면 0 )

 그리고 이 점화식을 기준으로 볼 경우, 위의 코드처럼 로직을 짤 수 있습니다. 우선 A와 B 지점을 정하고 그 선분 위의 C 지점을 차례대로 증가시키면서 체크합니다. 그리고 이전에 탐색했던 경우의 최대값이 더 큰 경우에는 해당 값을 그대로 유지합니다. A와 B를 잇는 선분이 있을 수도 있고, 없을 수도 있기 때문에 A+1부터 시작하는 것이 아니라 A부터 시작하여 C까지 C+1부터 시작하여 B-1까지, 그리고 A부터 B까지 잇는 경우가 있을 경우 + 1을 해주게 되는 것입니다.

 그리고 최종적으로 1 부터 100을 잇는 선분을 기준으로 생각하면 다른 모든 선분을 포함하고 있기 때문에, 이것이 바로 답이 됩니다.

P.S. 풀 때는 몰랐는데 지금 보니 플로이드-워셜 알고리즘이네요.