알고리즘 문제 풀어보자. 은하 전쟁!
* 문제: 은하 전쟁 은하계의 행성들이 전쟁을 벌이고 있다. 이 행성들은 너무 멀어서 아주 빠른 미사일로만 서로를 공격한다. 미사일은 100% 명중하며 기반시설에 일정한 피해를 입힌다. 기반시설 N 개일 때 단위시간당 N/10 개의 미사일을 생성한다. 10보다 작은 규모에서는 미사일이 생성되지 않는다. 미사일은 단위시간당 단위거리르 가며 N개의 미사일은 N개의 기반시설을 파괴한다. 기반시설은 복구되지 않으며 기반시설이 0이 되면 그 행성은 진다. 다음 데이터에는 각 행성의 위치와 초기 기반시설 규모가 적혀 있다. 모든 행성은 적대 관계이며, 가장 가까운 행성이 질 때까지 그 행성만 공격한다. 단, 공격자가 미리 상대가 질 것을 예상하고 목표를 수정하지는 않는다. 실제로 대상이 파괴될 때까지 공격을 계속한다. 전쟁 결과 마지막에 남는 별의 좌표를 적어라. (만약 살아남는 별이 없으면 '없음'이라고 적는다.) * 위치, 시간, 규모 등은 모두 정수이다. * 피격은 단위 시간 1이 흐른 뒤에 일어난다. * 단위 시간 안에 일어날 수 있는 피격이 모두 적용된 다음 미사일을 발사한다. * 행성 기반시설이 0이 되어도 날아가던 미사일은 계속 날아가 목표를 타격한다. * 미사일이 모두 없어져야 전쟁이 끝난다. -- 데이터 포맷 -- <별 위치 X> <별 위치 Y> <기반 시설 규모> <별 위치 X> <별 위치 Y> <기반 시설 규모> ... 예) 0 10 100 10 0 200 의 답은 (10, 0) * 풀어보기 #include <iostream> #include <vector> #include <math.h> using namespace std; int starNumber = 0; // 행성 수 vector<int> X; // 위치 X vector<int> Y; // 위치 Y vector
