프로그래머스 요격 시스템 (LV 2)

이번 문제는 A나라가 B 나라에 미사일 공격을 할 때, B가 A의 공격을 막아낼 수 있는 최소의 미사일 개수를 구하는 문제입니다.

A에서 발사된 미사일은 (s,e) 형태로 주어지고 지상과 평행한 직선으로 s~e 사이를 개구간으로 이동합니다.

B의 미사일은 x 지점에서 지상과 수직으로 날아가 x좌표에 걸쳐 있는 모든 A의 미사일을 격추시킬 수 있습니다.

 

targets, s와 e 입력의 범위가 큰 것을 확인했고 최대한 반복문을 자제해야겠다는 생각이 들었습니다.

처음 이 문제를 확인했을 때 관련된 문제를 풀어본 경험이 없어 어떻게 풀어야할지 생각이 떠오르지 않았습니다.

우선, 알고리즘적으로 어떤 미사일을 먼저 격추시키는 것이 최소한의 미사일을 사용할 것인지 생각했습니다.

 

시도 1.

e-s 크기가 작은 미사일에 대해서 격추시킬 x지점을 먼저 지정해주는 것이 미사일 개수를 줄일 수 있다고 생각했습니다.

넓은 범위의 미사일은 다른 미사일(좁은 범위의 미사일)을 위해 지정된 격추 미사일에 의해 맞을 확률이 더 크다고 생각했기 때문입니다.

하지만, e-s크기를 오름차순으로 정렬을 한다고 해도, s~e지점 중 어떤 지점을 선택해야 더 많은 미사일을 맞출 수 있는지 확인하려면 s,e지점을 순회하는 방법밖에 없다고 생각했습니다.

그래서 더 이상 진전시키지 않고 다른 방법을 찾게 되었습니다.

 

시도 2.

s,e 구간 중 s에 대해 내림차순으로 정렬을 한 다음 생각해보기로 했습니다. 여러 미사일 구간을 내림차순으로 정렬할 경우 다음과 같이 나타나게 됩니다.

내림차순 예시

여기서, 1번 미사일에 대해 살펴보도록 하겠습니다. 1번 미사일의 경우 s좌표가 가장 큰 미사일입니다. 그렇기 때문에 1번 미사일을 격추시키기 위해서는 s보다 큰 지점에 무조건 미사일을 배치해야됩니다. 그리고 문제에서 최소한의 미사일을 사용하도록 했으므로, 1번 미사일을 격추시키는 미사일을 통해 다른 미사일도 최대한 많이 격추시켜야만 합니다.

그렇기 때문에 1번을 요격시키기도 하고 다른 미사일도 맞추기 위해서는 s와 가장 가까운 지점에 미사일을 배치하는 것이 좋으므로 가장 최적의 장소는 s+1이 됩니다.

s+1 지점에 미사일을 배치할 경우 2,3,5 미사일이 동시에 제거됩니다. 그리고, 4번 미사일의 경우 또, 5번 이후의 미사일과 함께 격추시킬 수 있는 최적의 자리는 12지점이 됩니다. 이런식으로 진행을 한다면, 최소의 미사일을 사용할 수 있습니다.

 

증명

정렬된 미사일에서 s1+1은 s2보다 무조건 크게 된다.(이미 s2<=s1인 상태이므로)

여기서 e2가 s1+1보다 크다면, 2번 미사일은 1번 미사일과 함께 격추된다.

e2가 s1+1보다 작다면, 1번 미사일과 2번 미사일은 함께 격추될 수 없으므로 무조건 2개의 미사일을 사용해야합니다.

 

start지점을 s1+1로 지정하고 반복문을 통해 순회합니다.

i번째 미사일의 마지막 지점 ei가 start보다 크거나 같다면 해당 미사일은 현재 start를 지정한 미사일을 격추시키는 미사일과 함께 격추될 수 있으므로 그냥 넘어갑니다.

ei가 start보다 작다면 해당 미사일은 다른 미사일로 격추시켜야하므로 answer값에 1을 더해주고 start=si+1로 변경해줍니다.

 

 

 

 

 

사실 이문제는 여러 시도에 걸쳐 답이 나오고, 그 다음에 답이되는 이유를 찾았던 문제입니다. 그렇기 때문에 풀이 방법에 대한 증명도 한 번 해보게 되었습니다. 해당 풀이과정을 찾아보니 여러 포스팅에서 관련된 문제를 함께 제시해주기도 했는데, 이 후 이 문제에 대해서도 풀이해보는 시간을 가져야할 것 같습니다.