Lucent Blog

정답은 2번!

처음에 아무 생각 없이 1번으로 해서 틀렸는데, 그때 생각은 다음과 같았다:

오른쪽 끝을 기준으로 오름차순 정렬하면 Segment[i]와 Segment[j]가 겹친다면

그 사이의 모든 선분은 무조건 Segment[i]와 겹친다!

그러니까 각 선분을 선택할 때, 최대한 많이 묶어서 넘어가면 되겠지.

하지만 여기엔 큰 함정이 있었으니.. 다음 그림과 같은 데이터에서 최적해를 구하지 못한다.

위에서 빨간 숫자는 1번으로 정렬했을 때, 연두 숫자는 2번으로 정렬했을 때 각 선분의 인덱스이다.

그림에서 중요한것은 파란 선을 그어놓은 부분인데, 보다시피 빨간 인덱스에서는 1번과 4번을 함께 없애는 것을 구현할 수 없다(1번과 3번이 겹치지 않으므로)

하지만 연두 인덱스에서는 1번과 2번이므로 이 둘을 한 번에 없앨 수 있고, 당연히 비용은 앞에서 없앨 수록 적으므로 이쪽이 최선이다.

그러므로 2번처럼 정렬하면 이후의 DP까지 했을 때 시간복잡도 O(kn^2)만에 답을 구할 수 있다.

DP테이블을 d[레이저를 쏜 횟수][몇 번째 구름까지 없앴나] 로 정의하면,

와 같이 구할 수 있다(모든 인덱스는 1부터 시작한다고 가정, d[0][0] = 0이라고 가정) -

물론 k+1부터 j까지 모든 구름이 겹치는 k만 가능!

최종 답은 d[0][n],,d[k][n]중 최솟값이다.

보자마자 생각났겠지만 이 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제이다.

그런데, 무턱대고 냈다가는 TLE라는 충격적인 결과를 볼 수 있다...!

이걸 넘어가기 위해서는, Leading Zero를 효과적으로 처리해야 한다.

잘 생각해보라.

이 문제를 똑바로 생각했다면..

현재 위치부터 몇 자리의 숫자를 하나로 생각할 것인가? 를 정하는 부분이 있을텐데,

현재 위치부터 아무리 많은 Leading Zero를 하나로 생각하더라도 0이고,

지금 수가 답이 아닌 이상 아무리 많이 선택해도 최적이 될 수 없음은 자명하다.

( e.g. 12340000000000000000000000000000000000000000000000000000000000000000510=61 의 식에서

현재 12,34까지 선택했다고 보자, 그럼 현재 합은 46일텐데, 여기서 0을 선택하나, 00을 선택하나, ...

아무 의미가 없다. 더하기는 하나 추가되었지만 합은 그대로니 최적일 리가 없지 않은가.

최적은 "12+34+000000000000000000..05+10=61"이니까 )

따라서 이런걸 무시하면 엄청난 속도 향상을 이뤄낼 수 있다.

이처럼 사소하지만 중요한 발견을 놓치지 말자.