🔗 문제 링크
📝 문제 설명
전기줄 문제는 두 개의 전봇대에 서로 연결된 전기줄들이 주어질 때,
전기줄들이 서로 교차하지 않도록 하기 위해 최소 몇 개의 전기줄을 제거해야 하는지를 구하는 문제임.
문제를 해결하는 핵심은 교차하지 않는 전기줄들의 최대 개수(즉, 최대 부분 수열)를 찾고,
전체 전기줄 개수에서 이를 빼면 제거해야 할 전기줄의 개수가 됨.
핵심 아이디어:
두 전봇대의 한쪽 전깃줄 번호에 따라 정렬한 후, 다른 한쪽 번호에 대해 최장 증가 부분 수열(LIS) 문제로 변환할 수 있음.
✅ 풀이 접근 방식
두 가지 접근법을 시도함:
1. DFS + 메모이제이션 (Top-down 방식)
-
상태 정의:
dp[ah][bh]는 현재 상태가(ah, bh)일 때,
조건을 만족하며 연결할 수 있는 전기줄들의 최대 개수임. -
전이:
- 입력된 모든 전기줄 정보
lineInfo는[a, b]형태로 주어짐. - 현재 상태
(ah, bh)보다 큰 좌표(a, b)(즉,ah < a && bh < b)인 전기줄을 선택하고,
dp[ah][bh] = max(dp[ah][bh], dfs(a, b) + 1)로 갱신함.
- 입력된 모든 전기줄 정보
-
최종 결과:
dfs(0, 0)을 호출해 전체 연결 가능한 최대 전기줄 개수를 구한 후,
전체 전기줄 수N에서 이를 빼면 제거해야 할 전기줄의 개수가 됨.
DFS + 메모이제이션 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N;
private static List<int[]> lineInfo = new ArrayList<>();
private static int[][] dp;
public static void main(String[] args) throws IOException {
setting();
// 정렬: 한쪽 전봇대 번호 기준으로 오름차순 정렬
Collections.sort(lineInfo, Comparator.comparingInt(o -> o[0]));
System.out.println(N - dfs(0, 0));
}
private static int dfs(int ah, int bh) {
if (dp[ah][bh] != -1) return dp[ah][bh];
dp[ah][bh] = 0;
for (int i = 0; i < lineInfo.size(); i++) {
int a = lineInfo.get(i)[0];
int b = lineInfo.get(i)[1];
if (ah < a && bh < b) {
dp[ah][bh] = Math.max(dp[ah][bh], dfs(a, b) + 1);
}
}
return dp[ah][bh];
}
private static void setting() throws IOException {
N = Integer.parseInt(br.readLine());
dp = new int[555][555];
for (int i = 0; i < 555; i++) {
Arrays.fill(dp[i], -1);
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
lineInfo.add(new int[]{a, b});
}
}
}2. Bottom-up 동적 계획법 (DP)
-
상태 정의 (오름차순 방식):
dp[ah][bh]는 (ah, bh)를 끝으로 하는 전기줄 연결의 최대 개수를 의미함. -
전이:
- 먼저, 전기줄 정보를
[a, b]형태로 저장한 후,
한쪽 전봇대 번호 기준으로 오름차순 정렬함. - 각 전기줄
(ah, bh)에 대해,
0 ≤ j < ah와0 ≤ k < bh인 모든 이전 상태를 탐색하여,
dp[ah][bh] = max(dp[ah][bh], dp[j][k] + 1)로 갱신함.
- 먼저, 전기줄 정보를
-
최종 결과:
모든 전기줄에 대해 dp값을 갱신한 후,
최대 연결 가능한 전기줄 개수answer를 구하고,
N - answer가 제거해야 할 전기줄의 개수가 됨.
Bottom-up DP 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N;
private static List<int[]> lineInfo = new ArrayList<>();
private static int[][] dp;
public static void main(String[] args) throws IOException {
setting();
// 전기줄 정보를 한쪽 전봇대 번호 기준으로 오름차순 정렬
Collections.sort(lineInfo, Comparator.comparingInt(o -> o[0]));
// dp 배열 초기화: -1은 더미값으로 사용하지 않고, 0부터 시작함.
int answer = 0;
for (int[] line : lineInfo) {
int ah = line[0];
int bh = line[1];
int best = 0;
// (ah, bh)보다 작은 좌표 (j, k) 중 최대 dp값 찾기
for (int j = 0; j < ah; j++) {
for (int k = 0; k < bh; k++) {
best = Math.max(best, dp[j][k]);
}
}
dp[ah][bh] = Math.max(dp[ah][bh], best + 1);
answer = Math.max(answer, dp[ah][bh]);
}
System.out.println(N - answer);
}
private static void setting() throws IOException {
N = Integer.parseInt(br.readLine());
dp = new int[555][555]; // 좌표 범위에 맞춰 dp 배열 생성 (문제 조건에 따라 조정)
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
lineInfo.add(new int[]{a, b});
}
}
}✅ 결론
-
DFS + 메모이제이션 (Top-down):
재귀를 이용해 현재 상태에서 선택할 수 있는 전기줄들을 탐색하며,
(ah, bh) < (a, b)조건을 만족할 때만 전이하여 최대 연결 개수를 구함.
코드가 직관적이지만, 재귀 깊이에 따라 스택 오버플로우 가능성이 있음. -
Bottom-up DP (오름차순 방식):
전기줄 정보를 정렬한 후,
각 상태에 대해(ah, bh)보다 작은 모든 상태를 탐색하여 dp값을 갱신함.
재귀 없이 반복문으로 처리하기 때문에,
메모리 사용과 시간 복잡도를 잘 조절할 수 있음.
두 방법 모두 최대 연결 가능한 전기줄의 개수를 구한 후, 전체 전기줄 수 N에서 빼면
제거해야 할 전기줄의 최소 개수를 구할 수 있음.
