[백준 2565번][Java] 전깃줄 - 이름만 바뀐 LIS 문제

 

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

바로 전에 LIS 문제를 풀었음에도 한참 헤맸습니다.

기존 LIS 로직을 그대로 쓰려면 입력 배열을 정렬할 필요가 있습니다. 정렬을 하지 않으려면 따로 처리를 해줘야 하는데 이 부분을 간과했네요.

 

정렬이 필요한 이유는 전깃줄이 꼬이는 조건과 관계가 있습니다.

줄 a,b가 있다고 할 때 줄이 꼬이지 않는 조건은 다음과 같습니다.

- a.start < b.start && a.end < b.end

- a.start > b.start && a.end > b.end

 

그리고 다음과 같은 배열을 정의합니다.

links[i] : A 전봇대의 i번째 자리와 연결된 전봇대 B의 자리를 반환 

 

links[i] start값을 기준으로 정렬되어 있다면 end의 값만 비교하면서 꼬였는지 판단이 가능하기 때문에 구현이 편해집니다.

start 값들이 오름차순이든 내림차순이든 다음 값보다 큰지 작은지가 보장이 되기 때문입니다.

 

 

  

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
	static int n;
	static List<Link> links = new ArrayList<>();
	static int[] cache;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader("testcase.txt");
//		InputReader reader = new InputReader();
		n = reader.readInt();
		cache = new int[501];
		Arrays.fill(cache, -1);
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			links.add(Link.create(u,v));
		}

		links.sort(Comparator.comparingInt(link -> link.start));

		int ret = 0;
		for (int i = 0; i < n; i++) {
			ret = max(lis(i), ret);
		}
		System.out.println(n-ret);
	}

	private static int lis(int index) {
		Link currentLink = links.get(index);
		if(cache[index] != -1) return cache[index];

		int ret = 1;
		for (int i = index+1; i < n; i++) {
			Link otherLink = links.get(i);
			if(currentLink.end < otherLink.end) {
				ret = max(lis(i)+1, ret);
			}
		}
		return cache[index] = ret;
	}

}
class Link {
	int start, end;
	private Link(int start, int end) {
		this.start = start;
		this.end = end;
	}
	public static Link create(int start, int end) {
		return new Link(start, end);
	}

	@Override
	public String toString() {
		return "Link{" +
				"start=" + start +
				", end=" + end +
				'}';
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}