백준 2565 풀이 (전깃줄, 다이나믹 프로그래밍, LIS)

이번 문제는 코드를 다 짜서 돌렸는데 잘나오길래 고렇게 했더니 하도 안나와서 LIS를 다시 적용해서 풀게된 문제이다.

다음과 같은 그림이 존재하는 경우 겹치는 선을 제거하여 몇개의 선을 최소로 제거해야 겹치지 않게 되는지 구하는 문제였다. 처음에는 각 연결별로 겹치는 부분을 구하고 가장 겹치는 선이 많은 줄을 하나씩 제거하여 제거되는 선을 찾으려고 했다.

1. 각 라인별로 겹치는 선을 찾는다.

2. 최댓값을 구하고 해당 인덱스를 찾는다.

3. 해당 인덱스를 제거하는 경우 다른 라인들과의 겹치는 선을 갱신한다.

4. 만약 모든 값이 0이하인 경우, 몇개의 라인을 없앴는지 확인한다.

line	1,8	3,9	2,2	4,1	6,4	10,10	9,7	7,6
cross	5	4	2	3	2	0	2	2
	x	4	1	2	1	0	1	1
		x	1	1	0	0	0	0
			x	0	0	0	0	0

그러나!!! 이걸로 코드를 짰는데 제출해도 매번 출력이 잘못되었다는 오류만 뿜어 댔다. 

그래서 고수의 코드를 슬쩍보니 LIS로 푸는 것을 알게 되었다.

 

원리는 아래와 같다.

(x,y)가 존재할때 x를 기준으로 정렬한다.

그럼 y의 리스트에서, LIS에 해당되는 부분수열은 겹치지 않는 최대값이 된다. 

1,8	1	8
3,9	2	2
2,2	3	9
4,1	4	1
6,4	6	4
10,10	7	6
9,7	9	7
7,6	10	10

즉, 겹치지 않는 최대라인을 구할수 있으니 이외의 값들만 제거하면 라인을 최대한 살리면서 불필요한 데이터만 제거하면 되는 것이다.

아니 이걸 어떻게 생각하지......ㄷㄷ

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2007 > 초등부 4번

이번에 푼 문제는 올림피아드의 초등부에 나온 문제라고 한다.

나는 대학생인데도 못풀었는데.... 이 나라의 미래가 밝다....ㅎ