11월 6일 - 교차하지 않는 원의 현들의 최대집합[BOJ/2673]

원의 둘레에 위치한 여러 점을 양 끝으로 가지는 선분(현)들이 서로 교차하지 않도록 최대한 많이 선택하는 문제를 다뤄봤다. 문제를 해결하기 위해 동적 계획법(DP)을 활용했으며, 점의 양 끝점을 잘 설정하고 이들을 연결하면서 최대 현 개수를 구하는 방식으로 접근했다.

문제 접근 방법

1. 동적 계획법(DP) 설계: DP 배열 dp[i][r]은 i에서 r까지의 구간 내에서 선택할 수 있는 최대 교차하지 않는 현의 개수를 저장한다. 각 점에 대한 끝점을 미리 저장한 후, 특정 점에서 시작하여 교차하지 않는 현들을 이어나가는 방식이다.

2. 기본값 설정 및 점의 연결 조건:

• 만약 i >= r이면 0을 반환하여, 시작점이 종료점 이상인 경우 더 이상 연결할 현이 없음을 표시한다.
• 점 i가 특정 끝점 A[i]를 가지는 경우, A[i]와 i를 연결할 때 가능한 최대 현의 개수를 계산하고 이를 dp[i][r]에 저장한다.

3. 최대 현 개수 계산: 점 i에서 r까지 탐색을 진행하며 dp 배열을 업데이트하고, 이전에 계산된 값을 재사용하여 효율적으로 최대 개수를 찾는다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[][] dp = new int[101][101]; // DP 배열
    static int[] A = new int[101]; // 각 점의 현 끝점 저장
    static int N;

    // 점 i와 r 사이에서 교차하지 않는 최대 현의 개수를 찾는 함수
    static int f(int i, int r) {
        if (i >= r) return 0; // 시작점이 종료점 이상이면 0 반환
        if (dp[i][r] != -1) return dp[i][r]; // 이미 계산된 경우 바로 반환

        dp[i][r] = f(i + 1, r); // 기본값: 다음 위치로 이동

        // 점 i가 현의 시작점인 경우 현의 양 끝을 연결해 가능한 최대 개수 계산
        if (A[i] != 0 && A[i] <= r) {
            dp[i][r] = Math.max(dp[i][r], f(i + 1, A[i] - 1) + f(A[i] + 1, r) + 1);
        }
        return dp[i][r];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int[] row : dp) Arrays.fill(row, -1); // DP 배열 초기화
        N = Integer.parseInt(br.readLine().trim()); // 현의 개수 입력

        // 각 현의 양 끝점 입력 처리
        while (N-- > 0) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            if (a > b) { // a가 더 크면 swap
                int temp = a;
                a = b;
                b = temp;
            }
            A[a] = b; // 점 a에 대해 b를 끝점으로 설정
        }

        // 최대 현의 개수 출력
        System.out.println(f(1, 100));
    }
}

코드 설명

1. 전역 변수 및 DP 배열 초기화:

static int[][] dp = new int[101][101]; // DP 배열
static int[] A = new int[101]; // 각 점의 현 끝점 저장
static int N;

• dp[i][r]: i에서 r까지 교차하지 않는 최대 현의 개수를 저장하는 2차원 DP 배열이다.
• A[i]: 각 점 i의 끝점 정보를 저장하는 배열이다. 현의 양 끝을 표현하기 위해 사용된다.

2. 점 i와 r 사이에서 최대 현을 찾는 재귀 함수 f:

static int f(int i, int r) {
    if (i >= r) return 0; // 시작점이 종료점 이상이면 0 반환
    if (dp[i][r] != -1) return dp[i][r]; // 이미 계산된 경우 바로 반환

    dp[i][r] = f(i + 1, r); // 기본값: 다음 위치로 이동

    // 점 i가 현의 시작점인 경우 현의 양 끝을 연결해 가능한 최대 개수 계산
    if (A[i] != 0 && A[i] <= r) {
        dp[i][r] = Math.max(dp[i][r], f(i + 1, A[i] - 1) + f(A[i] + 1, r) + 1);
    }
    return dp[i][r];
}

• f(i, r) 함수는 i에서 r 구간에서 교차하지 않는 최대 현의 개수를 구한다.
• i >= r인 경우 더 이상 연결할 수 있는 현이 없으므로 0을 반환한다.
• 이미 계산된 경우(dp[i][r] != -1) 저장된 값을 바로 반환해 중복 계산을 방지한다.
• 점 i가 특정 끝점 A[i]를 가지는 경우, 양 끝을 연결해 가능한 최대 개수를 계산하여 dp[i][r]에 저장한다.

3. 입력 처리 및 끝점 설정:

while (N-- > 0) {
    String[] input = br.readLine().split(" ");
    int a = Integer.parseInt(input[0]);
    int b = Integer.parseInt(input[1]);
    if (a > b) { // a가 더 크면 swap
        int temp = a;
        a = b;
        b = temp;
    }
    A[a] = b; // 점 a에 대해 b를 끝점으로 설정
}

• 각 현의 양 끝점을 입력받아 저장한다.
• a > b인 경우 두 값을 스왑하여 작은 값이 항상 시작점이 되도록 설정한다.

4. 결과 출력:

System.out.println(f(1, 100));

• f(1, 100)을 호출해 점 1부터 100까지 가능한 최대 현의 개수를 구하고 이를 출력한다.

So...

이 문제는 동적 계획법(DP)을 이용해 해결할 수 있는 전형적인 문제로, 중복 계산을 피하고 효율적인 접근을 위해 DP 배열을 활용했다. 점 i에서 끝점 r까지 교차하지 않는 현의 개수를 최대화하기 위해 재귀적으로 탐색하며, 중간에 저장된 결과를 재활용하는 방식으로 최적화했다. 이 방법을 통해 최대 현의 개수를 빠르고 정확하게 계산할 수 있었다.