[Pro][삼성] 15942번 : 외계인 침공 - 1

삼성 SWEA 15942 : 외계인 침공 

SW Expert Academy

 

 

[풀이 후기]
난이도 : ★★★☆ (Pro)
문제 종류 : Sort & Binary Search
해결 방법 : Merge Sort, Upper bound

 

* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능

---

 

문제

 

 

 

문제분석

1. 초기에 가진 함선 수(K)와 "동원"으로 추가된 함선을 이용해서, "침략"을 완성해야한다. 
2. 주민의 수가 최대 10억 이므로, "동원"을 고려하면, 함선의 수는 int 범위를 넘을 수 있음에 주의하자. 
3. "동원"을 최소화 하기 위해서, "침략"을 어떤 순서로 해야하는지 고민해보자. 

 

---

 

접근 방법

이 문제의 핵심은 "동원을 최소화 하기 위해, 침략 순서를 어떻게 정할  것인가?" 이다. 

 

 

결론부터 말하면, 아래 과정을 통해서 동원을 최소화 할 수 있다. 

1. 모든 행성 정복에 필요한 함선 수를 계산한다. (= 모든 행성의 인원 수를 더한다.)
2. "현재 함선 수 이하의 주민이 있는 행성 중, 가장 주민이 많은 행성"을 고른다. 
3. "침략"을 진행한 뒤, 함선이 더 필요한 경우에 "동원" 한다. 
3. 1번 과정과 동일하게, 다음으로 침략할 행성을 고른다. 
4. 반복한다. 

 

 

 

위 과정 중, 포인트는 "현재 함선 수 이하의 주민이 있는 행성 중, 가장 주민이 많은 행성" 이다. 

 

이러한 행성의 위치는 Upper bound 알고리즘을 활용해서 구할 수 있다.

 

Upper bound는 key 값 초과가 처음으로 나오는 index를 return 하므로, 
(index - 1) 은 key 값 이하 중, 가장 값이 큰 index가 된다. 

 

 

 

 

* Upper Bound 에 관한 내용은 아래 포스팅을 참고하자. 

[알고리즘][탐색][C/C++] Lower Bound, Upper Bound

[알고리즘][탐색][C/C++] Lower Bound, Upper Bound

 

 

 

예시로 확인해보자. 

 

N=7, K=2 이고, 아래와 같이 행성 인원 수에 따라 정렬해둔 상태라고 하자. 

현재 함선 수 (K) 이하 중, 가장 주민이 많은 행성은 Upper bound 결과 - 1 과 동일하다. 

 

따라서, 처음 "침략" 해야할 행성은 2번 행성이 된다. 

 

K=2 일 때, "침략" 해야할 행성

 

 

 

 

함선 수가 더 필요하므로, "동원"을 진행하여, K=4 가 된다. 

따라서, 다음으로 "침략" 해야할 행성은 4번 행성이 된다. 

K=4 일 때, "침략" 해야할 행성

 

 

함선 수가 더 필요하므로, "동원"을 진행하여, K=8 이 된다. 

따라서, 다음으로 "침략" 해야할 행성은 5번 행성이 된다. 

K=8 일 때, "침략" 해야할 행성

 

 

 

 

 

위 과정을 반복하다보면, 아래와 같은 상황에서 문제에 봉착한다. 

K=24 이므로, 6번 행성을 골라야하는데, (Upper bound - 1) 을 하게 되면, 7번 행성을 고르게 된다. 

이미 "침략"한 7번 행성은 피할 수 있도록, visited 처리를 하자. 

K=24 일 때, "침략" 해야할 행성

 

 

visited 처리는 어떻게 해야할까?

 

"침략"을 진행한 경우, visited[ i ] = 1 로 표시를 하고, 아래 코드처럼 한칸씩 검사를 해야한다면,

최악의 경우, N만큼의 while 반복문 실행이 계속될 것이므로, 다른 방법이 필요하다. 

int p = upperBound(K) - 1;
while (visited[p]) p--;

 

 

 

효율적으로 visited 처리할 방법이 필요하다. 

 

 

 

 

이 방법에 대해서는 다음 포스팅에서 다뤄보겠습니다. 

 

[Pro][삼성] 15942번 : 외계인 침공 - 2

[Pro][삼성] 15942번 : 외계인 침공 - 2