[SWEA] 무선 충전 (java)

아아앗악아아악 발표에 걸렸다. 자세히 정리해보도록 하자,,

 

문제 이해

1. 사용자 A와 B가 있다. 두 사용자는 동시에 움직인다.

2. 매초마다 이동 한다. 만약 이동한 좌표의 위치가 BC에 들어오면 접속이 가능하다.

3. 이렇게 BC에 들어올 때마다 충전량을 합한 최대값을 찾아야한다.

첫 번째 시도

사용자가 두 명밖에 없어서 사용자가 m만큼 움직일 때마다 저장되는 충전량을 더하려고 했다.

그래서 이차원 배열 map을 만들어서 BC의 성능을 저장하려고 했다.

맨해튼 거리를 이용해서 충전 범위에 들어오는 map의 좌표값에 P(성능)을 저장하는 것이다.

c >= Math.abs(x-i) + Math.abs(y-j)

 

 

 

 

두 번째 시도

근데 생각을 해보니 BC가 겹칠 수가 있었다. 그래서 이차원 배열을 이용하는 게 아니라는 생각이 들었고,

그러면 arrayList 타입인 배열을 써서 겹치는 좌표값을 다 넣어볼까 라는 생각이 들었지만,

항상 최대값을 구하는 조건을 생각해서 구하는 게 복잡하고 비효율적이라고 생각했다.

 

다른 방법을 찾아보자!

각 시간(m번)에서 A와 B가 각각 모든 충전소에 대해 충전할 수 있는지만 확인하면 된다.

그래서 bc에 대해 2개를 포함하는 중복 조합만 찾으면 되었다. 

포인트는 A와 B가 같은 bc안에 들어가는지 들어가지 않는지에 대한 유무이다!

 

만약 두 플레이어가 다른 충전소를 사용하는 경우, 충전량을 합산하면 된다.

만약 두 플레이어가 같은 충전소를 사용하는 경우, 두 플레이어는 충전량을 공유하면된다.

 

따라서,

1. 매 시간마다 bc에 대해 2개를 포함하는 중복조합을 만든다. (충전소 개수 bc * bc)

2. 조합 중에서 두 플레이어가 얻을 수 있는 최대 충전량을 계산한다. (M번 반복)

 

시간 복잡도는 O(M * bc^2)이다. 최대 M=100, bc=8이니까 100*8*8 =6400 연산을 하면 된다.

 

 

 

코드보러가기