SWEA 5644 무선충전 Java, Python
OnlineJudge

SWEA 5644 무선충전 Java, Python

반응형

 

문제로이동

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


목차

     


     


    문제 설명

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

    이미 필드의 크기가 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);
    	}
    }
    반응형