문제 설명
시뮬레이션/구현 문제입니다.
이미 필드의 크기가 10*10으로 고정되어 있고 주인공의 위치도 고정되어 있어 수월하게 접근 가능했습니다.
BC의 위치와 세기, 허용 거리가 다르기 때문에 이를 중점적으로 어떻게 계산할 것인지 판단해야 합니다.
저는 두 주인공을 동시에 움직이면서 매 이동마다(t=0부터) 모든 BC와 거리를 계산했고
주인공 A, 주인공 B가 사용할 수 있는 BC를 리스트에 담았습니다.
정리하자면, 로직은 아래와 같습니다.
입력조건
BC를 입력 받을 때 POWER를 내림차순으로 정렬해 줍니다.(이후에 따로 정렬할 필요가 없어집니다)
- 모든 BC와 거리계산하여 사용 가능한 BC를 주인공A, 주인공B의 어레이에 각각 담아줍니다.
- 만약, 사용가능한 BC가 둘 다 없다면 넘어갑니다.
- 사용가능한 BC 목록중 가장 앞의 BC가 같은지 확인합니다.
- 한 BC를 공유하는 것((A+B)/2)이 가장 큰가?
- 다른 BC를 쓸 수는 없는가?
- 주인공을 이동시킵니다.
순서를 잘 보시면 선 이동이 아닌 연산 후 이동입니다.
문제에도 명시되어 있듯이 t=0 일 때도 BC가 사용가능 할 수 있으므로 반드시 연산 후 이동하셔야 합니다.
JAVA코드 이후에 Python을 작성했는데 Python이 좀 더 간결해 보입니다.
저처럼 굳이 리스트를 받아서 할 필요 없이 필드의 크기가 작기 때문에 2중 for문을 돌리는 것도 좋은 방법입니다.
소스 코드
Python
T = int(input())
direction = [[0,0],[0,-1],[1,0],[0,1],[-1,0]]
for t in range(1,T+1):
posA=[1,1]; posB=[10,10]
M,A = map(int,input().split())
ma = list(map(int,input().split()))
mb = list(map(int,input().split()))
aps = [list(map(int,input().split())) for _ in range(A)]
aps = sorted(aps,key = lambda x:-x[3])
answer = 0
for time in range(M+1):
al = list(); bl=list()
for idx in range(len(aps)):
if abs(aps[idx][0]-posA[0])+abs(aps[idx][1]-posA[1])<=aps[idx][2]:al.append(idx)
if abs(aps[idx][0]-posB[0])+abs(aps[idx][1]-posB[1])<=aps[idx][2]:bl.append(idx)
curmax = 0
if al or bl:
if al and bl:
if al[0]==bl[0]:
if len(al)>1:curmax = max(curmax, aps[al[1]][3]+aps[bl[0]][3])
if len(bl)>1:curmax = max(curmax, aps[bl[1]][3]+aps[al[0]][3])
else:
curmax = max(curmax, aps[al[0]][3]+aps[bl[0]][3])
if al:curmax = max(curmax,aps[al[0]][3])
if bl:curmax = max(curmax,aps[bl[0]][3])
answer += curmax
if time==M:continue
posA[0]+=direction[ma[time]][0]
posA[1]+=direction[ma[time]][1]
posB[0]+=direction[mb[time]][0]
posB[1]+=direction[mb[time]][1]
print('#{} {}'.format(t,answer)) Java8
package swea5644;
import java.util.*;
import java.io.*;
public class Solution {
static StringBuilder sb = new StringBuilder();
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int M,A,moveA[],moveB[],answer,AX,AY,BX,BY;
static int[][] direction = new int[][] {{0,0},{0,-1},{1,0},{0,1},{-1,0}};//X상우하좌
static ArrayList<AP> aps;
static class AP implements Comparable<AP>{
int x,y,length,power;
public AP(int x, int y, int length, int power) {
this.x = x;
this.y = y;
this.length = length;
this.power = power;
}
@Override
public int compareTo(AP o) {
return o.power-this.power;//파워 큰 순 정렬
}
}
static void move() {
AX=0;AY=0;BX=9;BY=9;
for(int t=0;t<=M;t++) {
int maxP = 0; //이번 시간에서 얻을 수 있는 최대 파워
//가능한 AP 수집
ArrayList<Integer> aPos = new ArrayList<>();
ArrayList<Integer> bPos = new ArrayList<>();
for(int i=0;i<A;i++) {//각 송신기별 거리 탐색
AP ap = aps.get(i);
int da = Math.abs(AX-ap.x) + Math.abs(AY-ap.y);
int db = Math.abs(BX-ap.x) + Math.abs(BY-ap.y);
if(ap.length>=da)aPos.add(i);
if(ap.length>=db)bPos.add(i);
}
if(!aPos.isEmpty()||!bPos.isEmpty()) {
if(!aPos.isEmpty() && !bPos.isEmpty()) {//둘 다 가능한 AP가 있을 때
if(aPos.get(0)==bPos.get(0)) {//만약 둘 다 최고 파워가 같은 AP라면
if(aPos.size()>=2) maxP = Math.max(aps.get(aPos.get(1)).power+aps.get(bPos.get(0)).power,maxP);
if(bPos.size()>=2) maxP = Math.max(aps.get(aPos.get(0)).power+aps.get(bPos.get(1)).power,maxP);
}
else maxP = Math.max(aps.get(aPos.get(0)).power+aps.get(bPos.get(0)).power,maxP);
}
if(!aPos.isEmpty()) maxP = Math.max(aps.get(aPos.get(0)).power,maxP);
if(!bPos.isEmpty()) maxP = Math.max(aps.get(bPos.get(0)).power,maxP);
answer+=maxP;
}
if(t==M)continue;
AX += direction[moveA[t]][0];
AY += direction[moveA[t]][1];
BX += direction[moveB[t]][0];
BY += direction[moveB[t]][1];
}
}
static void input() throws IOException {
int T = stoi(br.readLine());
for(int t=1;t<=T;t++) {
answer = 0;
st = new StringTokenizer(br.readLine());
M = stoi(st.nextToken());//필드크기
A = stoi(st.nextToken());//BC갯수
moveA = new int[M];
moveB = new int[M];
st = new StringTokenizer(br.readLine());
for(int i =0;i<M;i++)moveA[i]=stoi(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i =0;i<M;i++)moveB[i]=stoi(st.nextToken());
aps = new ArrayList<>();
for(int i=0;i<A;i++) {
st = new StringTokenizer(br.readLine());
aps.add(new AP(stoi(st.nextToken())-1,stoi(st.nextToken())-1,stoi(st.nextToken()),stoi(st.nextToken())));
}
Collections.sort(aps);
move();
sb.append("#").append(t).append(" ").append(answer).append("\n");
}
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
input();
System.out.println(sb);
}
}