5644 무선 충전

 

BC에 대한 중복을 어떻게 처리할 것인지가 가장 어려웠던 부분.

처음 작성한 것이 오답인데 해결이 잘 안됐으나 아래의 참조사이트의 비교 구문을 사용 후 Pass 되었다.

 

ArrayList 2개에서 maxP를 구하는 부분이 핵심이다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class BC {
	int x, y, c, p;

	BC(int x, int y, int c, int p) {
		this.x = x;
		this.y = y;
		this.c = c;
		this.p = p;
	}

	public boolean isCovered(P p) {
		return (Math.abs(p.x - x) + Math.abs(p.y - y) <= c);
	}

}

class P {
	int x, y;

	P(int x, int y) {
		this.x = x;
		this.y = y;
	}

}

class Solution {

	static int M, A;

	private static boolean DBG = false;
	private static int ans;

	static int[][] player;
	static int[] dx = { 0, 0, 1, 0, -1 };
	static int[] dy = { 0, -1, 0, 1, 0 };
	static BC[] bcList;
	static P[] pList;
	static ArrayList<Integer> scores;
	static Queue<P>[] Q;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			A = Integer.parseInt(st.nextToken());

			// 시작점을 테스트하기 위해 0번 인덱스를 비워둠
			player = new int[2][M + 1];
			scores = new ArrayList<>();
			for (int i = 0; i < 2; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 1; j <= M; j++) {
					player[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			pList = new P[2];
			pList[0] = new P(1, 1);
			pList[1] = new P(10, 10);

			bcList = new BC[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());
				bcList[i] = new BC(x, y, c, p);
			}
			// level, time, sum
			simulation();
			ans = 0;
			for (int v : scores) {
				ans += v;
			}

			System.out.println("#" + test_case + " " + ans);
		}
	}

	private static void simulation() {
		int time = 0;

		while (true) {
			ArrayList<BC>[] power = new ArrayList[2];
			power[0] = new ArrayList<BC>();
			power[1] = new ArrayList<BC>();

			if (time == M + 1) {
				break;
			}

			for (int i = 0; i < 2; i++) {
				P p = pList[i];

				int nx = p.x + dx[player[i][time]];
				int ny = p.y + dy[player[i][time]];

				p.x = nx;
				p.y = ny;

				for (int j = 0; j < A; j++) {
					BC bc = bcList[j];
					if (bc.isCovered(p)) {
						power[i].add(bc);
					}
				}

			}

			for (int i = 0; i < 2; i++) {
				Collections.sort(power[i], (a, b) -> {
					return b.p - a.p;
				});
			}

			int maxP = 0;
			if (!power[0].isEmpty() || !power[1].isEmpty()) {
				//둘다 요소가 있는 경우
				if (!power[0].isEmpty() && !power[1].isEmpty()) {
					if (power[0].get(0) == power[1].get(0)) {
						if (power[0].size() >= 2)
							maxP = Math.max(power[0].get(0).p + power[0].get(1).p, maxP);
						if (power[1].size() >= 2)
							maxP = Math.max(power[1].get(0).p + power[1].get(1).p, maxP);
                        //이부분에서 사이즈가 1인 경우는 고려되지 않았음.
                        //아래의 코드를 추가 후, else를 추가하여 가독성을 높일 수 있음.
                        //중복된 BC가 있기 떄문에 power1/0 둘중 아무거나 택한다.
                        maxP = Math.max(power[1].get(0).p, maxP);
					} else {
						maxP = Math.max(power[0].get(0).p + power[1].get(0).p, maxP);
					}
                } else {//둘 중 하나만 요소가 있는 경우
                    if (!power[0].isEmpty())
                        maxP = Math.max(power[0].get(0).p, maxP);
                    if (!power[1].isEmpty())
                        maxP = Math.max(power[1].get(0).p, maxP);
                }

			}
			scores.add(maxP);

			time++;
		}
	}

}

 

 

참조 사이트 : https://imksh.com/54