BOJ_2673_교차하지 않는 원의 현들의 최대 집합 (Java)

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

문제 링크

성능 요약

메모리: 12056 KB, 시간: 84 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 11월 20일 14:36:19

문제 설명

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

단, 1 ≤ N ≤ 50이고, 주어진 각 점은 많아야 한 현의 끝점이 될 수 있다.

입력

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

출력

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

문제 풀이

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int N, line[][], dp[][];
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	/*
	 * 교차되지 않는 정답군 크기를 dp로 저장할거고 그 dp배열 채울 값을 구간으로 정의하여 구분.
	 * i~j구간의 정답크기는 dp[i][j]로. 이때 이를 작은 부분으로 쪼개면 i<=mid<j일 때
	 * dp[i][j]를 갱신하려면 dp[i][mid] + dp[mid][j]로 쪼갤 수 있다.
	 * 또한 구간 전체를 길이로 하는 선분도 고려해야하므로 이를 검색해 더해줌.
	 */
	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		line = new int[101][101];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			line[A][B]++;
			line[B][A]++;
		}
		
		dp = new int[101][101];
		for(int i=1; i<=100; i++) {
			for(int j=i; j>=1; j--) {
				for(int mid = j; mid<i; mid++) {
					dp[j][i] = Math.max(dp[j][i], dp[j][mid] + dp[mid][i] + line[j][i]);
				}
			}
		}
		bw.write(String.valueOf(dp[1][100]));

		bw.flush();
		bw.close();
		br.close();
	}
}