SWEA 5644 무선충전 Java, Python

 

문제로이동

SW Expert Academy

---

목차

 

---

 

---

문제 설명

시뮬레이션/구현 문제입니다.

이미 필드의 크기가 10*10으로 고정되어 있고 주인공의 위치도 고정되어 있어 수월하게 접근 가능했습니다.

BC의 위치와 세기, 허용 거리가 다르기 때문에 이를 중점적으로 어떻게 계산할 것인지 판단해야 합니다.

 

저는 두 주인공을 동시에 움직이면서 매 이동마다(t=0부터) 모든 BC와 거리를 계산했고

주인공 A, 주인공 B가 사용할 수 있는 BC를 리스트에 담았습니다.

정리하자면, 로직은 아래와 같습니다.

 

입력조건

BC를 입력 받을 때 POWER를 내림차순으로 정렬해 줍니다.(이후에 따로 정렬할 필요가 없어집니다)

 

1. 모든 BC와 거리계산하여 사용 가능한 BC를 주인공A, 주인공B의 어레이에 각각 담아줍니다.
2. 만약, 사용가능한 BC가 둘 다 없다면 넘어갑니다.
3. 사용가능한 BC 목록중 가장 앞의 BC가 같은지 확인합니다.
   1. 한 BC를 공유하는 것((A+B)/2)이 가장 큰가?
   2. 다른 BC를 쓸 수는 없는가?
4. 주인공을 이동시킵니다.

순서를 잘 보시면 선 이동이 아닌 연산 후 이동입니다.

문제에도 명시되어 있듯이 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);
	}
}