BOJ 1150 - 백업

이번에도 그리디로 돌아왔다.

아마도 내 4번째 다이아 문제가 아닐까 한다...

지금까지 푼 다이아 문제 중 가장 어려웠던 것 같다.

가장 오랜 시간 고민하다가 결국 다른 방법을 찾아봐서 풀었던 기억이 난다.

 

---

체감 티어: D4

 

문제는 우리에게 단순한 것을 요구한다.

그저 k 개의 네트워크 케이블을 이용해 회사들을 연결하는데 가장 길이가 짧게 하는 것이다.

예제를 가지고 간단하게 살펴보자, 우선 0km부터 가장 가까운 회사부터 A, B, C, D, E라고 정의하겠다.

 

A-B의 길이는 3-1=2km,

B-C의 길이는 4-3=1km,

C-D의 길이는 6-4=2km,

D-E의 길이는 12-6=6km이다.

여기서 가장 길이가 짧게 가져갈 수 있는 방법은 A-B와 C-D를 선택하는 것이다.

문제에서 말했듯 이미 회사끼리 연결한 회사는 선택할 수 없다는 조건이 있다.

 

어떻게 로직을 짜야 A-B, C-D를 선택하는 프로그램을 작성할 수 있을까?

 

우선 길이가 가장 짧은 부분의 회사부터 네트워크 케이블을 사용한다고 해보자. 그럼 B-C를 선택하게 된다. 그럼 A와 D를 사용할 수 없다. 하지만 해답은 A와 D를 선택해 포함하는 것이다.  이미 B-C 선택하였음으로 이를 제외하고 A-D를 선택하는 상황을 고려하기 위해 (A-D) - (B-C)로 만들어준다. A-D에서 B-C를 빼 A-D를 선택하는 것과 같은 상황을 만들 수 있다. 이미 사용되었던 B또는 C회사와 연결된 네트워크 케이블을 연결하는 방법은 제외하며 선택한다.

이제 이 행동을 k번 하면 k개의 네트워크 케이블을 선택한 것과 같다.