알고리즘 문제 풀어보자. 은하 전쟁!



* 문제: 은하 전쟁

은하계의 행성들이 전쟁을 벌이고 있다. 이 행성들은 너무 멀어서 아주 빠른 미사일로만 서로를 공격한다. 미사일은 100% 명중하며 기반시설에 일정한 피해를 입힌다. 기반시설 N 개일 때 단위시간당 N/10 개의 미사일을 생성한다. 10보다 작은 규모에서는 미사일이 생성되지 않는다. 미사일은 단위시간당 단위거리르 가며 N개의 미사일은 N개의 기반시설을 파괴한다. 기반시설은 복구되지 않으며 기반시설이 0이 되면 그 행성은 진다.

다음 데이터에는 각 행성의 위치와 초기 기반시설 규모가 적혀 있다. 모든 행성은 적대 관계이며, 가장 가까운 행성이 질 때까지 그 행성만 공격한다. 단, 공격자가 미리 상대가 질 것을 예상하고 목표를 수정하지는 않는다. 실제로 대상이 파괴될 때까지 공격을 계속한다.

전쟁 결과 마지막에 남는 별의 좌표를 적어라. (만약 살아남는 별이 없으면 '없음'이라고 적는다.)

* 위치, 시간, 규모 등은 모두 정수이다.
* 피격은 단위 시간 1이 흐른 뒤에 일어난다.

* 단위 시간 안에 일어날 수 있는 피격이 모두 적용된 다음 미사일을 발사한다.
* 행성 기반시설이 0이 되어도 날아가던 미사일은 계속 날아가 목표를 타격한다.
* 미사일이 모두 없어져야 전쟁이 끝난다.

-- 데이터 포맷 --
<별 위치 X> <별 위치 Y> <기반 시설 규모>
<별 위치 X> <별 위치 Y> <기반 시설 규모>
...

예)
0 10 100
10 0 200

의 답은 (10, 0)


* 풀어보기




* 실행 결과 1

행성의 숫자를 입력: 2
0 10 100
10 0 200

행성1 (0,10) N:100-> target: 행성 2(10,0)
행성2 (10,0) N:200-> target: 행성 1(0,10)
행성1 (0,10) 파괴!!!

Winner: 0 10



* 실행 결과 2

행성의 숫자를 입력: 3
0 10 100
10 0 200
3 5 300

행성1 (0,10) N:100-> target: 행성 3(3,5)
행성2 (10,0) N:200-> target: 행성 3(3,5)
행성3 (3,5) N:300-> target: 행성 1(0,10)
행성1 (0,10) 파괴!!!

행성1 (10,0) N:200-> target: 행성 2(3,5)
행성2 (3,5) N:198-> target: 행성 1(10,0)
행성2 (3,5) 파괴!!!

Winner: 10 0


* 실행 결과 3

행성의 숫자를 입력: 2
0 10 100
10 0 100

행성1 (0,10) N:100-> target: 행성 2(10,0)
행성2 (10,0) N:100-> target: 행성 1(0,10)

[생존 행성] 미사일 모두 사용!
(0,10) 남은 기반시설:9
(10,0) 남은 기반시설:9


Popular posts from this blog

알고리즘 연습 (셀프 넘버 합 구하기)