[SWEA 5644] 무선 충전 자바

문제

SW Expert Academy

메모리 : 26,560KB , 시간 : 229ms

접근방식

• 배터리의 범위만큼 ArrayList에 담아줌. 각 리스트는 0번 배터리, 1번 배터리..의 범위를 가짐
• A,B의 이동궤적을 배열에 저장해줌.
• 움직이는 것은 time을 증가시키면서 A,B의 위치에서 배터리의 범위에 포함되는 지를 확인함.(A,B 위치의 배터리를 조합하여 최대값을 찾는다고 이해함)
• A,B가 같은 배터리 범위 내에 있는 경우에는 값을 반으로 나눠줌. 이때 A,B가 값을 가지는지 확인하지 않아서 케이스 한 개에 걸렸었음

//배터리 리스트
for (int i = 0; i < list.length; i++) {
    powerA = 0;
    for (Point p : list[i]) {
        if(p.x == aPos.x && p.y == aPos.y) {
            powerA = p.power;
        }
        for (int j = 0; j < list.length; j++) {
            powerB = 0;
            for(Point p2 : list[j]) {
                if(p2.x == bPos.x && p2.y == bPos.y) {
                    powerB = p2.power;
                }
            }
            //같은 배터리에 있는 경우
            if(i==j && powerA !=0 && powerB!=0) {
                max = Math.max(max, (powerA+powerB)/2);
            }else{
                max = Math.max(max, powerA+powerB);
            }
        }
    }
}

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.StringTokenizer;

class Point{
	int x;
	int y;
	int power;
	Point(int x,int y){
		this.x = x;
		this.y = y;
	}
	Point(int x,int y,int power){
		this.x = x;
		this.y = y;
		this.power = power;
	}
}

public class Solution {
	static int M,A,answer;
	static int[] movingA,movingB;
	static int[] dx = {0,-1,0,1,0};
	static int[] dy = {0,0,1,0,-1};
	static Point aPos,bPos;
	static ArrayList<Point>[] list;
	
	static void moveUser(int time) {
		if(time == M+1) {
			return;
		}
		//배터리 영역에 속해있는 지 확인
		int max = 0;
		int powerA = 0,powerB=0;
		//배터리 리스트
		for (int i = 0; i < list.length; i++) {
			powerA = 0;
			for (Point p : list[i]) {
				if(p.x == aPos.x && p.y == aPos.y) {
					powerA = p.power;
				}
				for (int j = 0; j < list.length; j++) {
					powerB = 0;
					for(Point p2 : list[j]) {
						if(p2.x == bPos.x && p2.y == bPos.y) {
							powerB = p2.power;
						}
					}
					//같은 배터리에 있는 경우
					if(i==j && powerA !=0 && powerB!=0) {
						max = Math.max(max, (powerA+powerB)/2);
					}else{
						max = Math.max(max, powerA+powerB);
					}
				}
			}
		}
		//System.out.println(time+" "+max);
		answer += max;
		//시간별로 이동
		aPos.x +=  dx[movingA[time]];
		aPos.y +=  dy[movingA[time]];
		bPos.x +=  dx[movingB[time]];
		bPos.y +=  dy[movingB[time]];
				
		
		moveUser(time+1);
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		StringBuilder sb = new StringBuilder();
		
		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			A = Integer.parseInt(st.nextToken());
			movingA = new int[M+1];
			movingB = new int[M+1];
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				movingA[i] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				movingB[i] = Integer.parseInt(st.nextToken());
			}
			list = new ArrayList[A];
			 
			for (int i = 0; i < A; i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				int p = Integer.parseInt(st.nextToken());
				list[i] = new ArrayList<>();
				
				for (int j = x-c; j <= x+c; j++) {
					for (int k = y-c; k <= y+c; k++) {
						if(j >=0 && j <= 10 && k >=0 && k <= 10 ) {
							for (int cov = 0; cov <= c; cov++) {
								//배터리 범위만큼 list에 넣어줌
								if(cov == Math.abs(j-x)+Math.abs(k-y)) {
									list[i].add(new Point(k,j,p));
									//System.out.println(k+" "+j);
								}
							}
						}
					}
				}
			}
		 
			aPos = new Point(1,1);
			bPos = new Point(10,10);
			answer = 0;
			moveUser(0);
			sb.append("#").append(t).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
}