(Java/자바) - SWEA 5644번 : 무선 충전

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo 

SW Expert Academy

---

• 문제 : 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

 

 

---

• 풀이 :

구현 및 시뮬레이션 문제였습니다.

 

알고리즘은 다음과 같은 형태로 진행됩니다.

 

0. BC의 정보를 충전량 기준 내림차순으로 정렬

 

1. 현재 칸에서 충전할 수 있는 BC를 찾는다. BC를 충전하는 경우는 총 3가지이다.

  1-1 BC 범위 안에 A, B 두 사람이 존재하는 경우

  1-2 BC 범위 안에 A만 존재하는 경우

  1-3 BC 범위 안에 B만 존재하는 경우

 

1-1의 경우 어떠한 경우에도 반드시 그 BC를 충전할 수 있으므로 (BC가 내림차순이며 A, B 두 명만 있기 때문) 그 때의 충전값을 정답에 더한다.

 

1-2의 경우 해당 BC는 반드시 A를 선택해야 한다. 이 때, A가 다른 BC의 영역에 겹쳐있을 수 있으므로 현재 탐색중인 BC에서 A를 충전시킨다는 의미의 플래그를 세운다. 이 또한 BC가 내림차순으로 정렬되었기에 항상 유효하다.

 

1-3의 경우 1-2와 같은 방법으로 진행한다.

 

 

2. 다음 칸으로 이동한다.

 

3. M만큼 반복한다.

 

 

 

 

 

 

---

• 소스코드 : 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Solution{
	static int TC, M, A, sum, answer;
	static int[] moveA, moveB, currA, currB;
	static int[][] BC;
	static int[] dx = {0,-1,0,1,0};
	static int[] dy = {0,0,1,0,-1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		StringTokenizer st2;
		TC = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= TC; testCase++) {
			sb.append("#").append(testCase).append(" ");
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			A = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			st2 = new StringTokenizer(br.readLine());
			moveA = new int[M];
			moveB = new int[M];
			currA = new int[2];
			currB = new int[2];
			currA[0] = currA[1] = 1;
			currB[0] = currB[1] = 10;
			BC = new int[A][4];
			answer = 0;
			for (int i = 0; i < M; i++) {
				moveA[i] = Integer.parseInt(st.nextToken());
				moveB[i] = Integer.parseInt(st2.nextToken());
			}
			for (int i = 0; i < A; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 4; j++) {
					BC[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			Arrays.sort(BC, new Comparator<int[]>(){
				@Override
				public int compare(int[] o1, int[] o2) {
					return o2[3] - o1[3];
				}
			});
			
			
			charge();
			for (int i = 0; i < M; i++) {
				/*
				 * 1. 한 칸 이동
				 * 2. 이동한 방향에서 충전할 수 있는 BC 찾음
				 * 3. 해당 BC로 충전
				 * */
				move(i);
				charge();
				System.out.println(answer);
			}
			sb.append(answer).append("\n");
		}
		System.out.println(sb.toString());
	}
	private static void charge() {
		int cnt = 2;
		int distanceA;
		int distanceB;
		boolean usingA = false;
		boolean usingB = false;
		
		for (int i = 0; i < BC.length; i++) {
			distanceA = calc(i,'A');
			distanceB = calc(i,'B');
			if (distanceA <= BC[i][2] && distanceB <= BC[i][2]) {
				answer += BC[i][3];
				cnt--;
			} else if (distanceA <= BC[i][2]){
				if(!usingA) {
					usingA = true;
					answer += BC[i][3];
					cnt--;
				}
			} else if (distanceB <= BC[i][2]){
				if (!usingB) {
					usingB = true;
					answer += BC[i][3];
					cnt--;
				}
			}
			if (cnt == 0) {
				break;
			}
		}
	}
	
	private static int calc(int i, char type) {
		switch (type) {
		case 'A':
			return Math.abs((BC[i][0] - currA[0])) + Math.abs((BC[i][1] - currA[1]));
		case 'B':
			return Math.abs((BC[i][0] - currB[0])) + Math.abs((BC[i][1] - currB[1]));
		}
		return 0;
	}
	
	
	
	private static void move(int i) {
		currA[1] += dx[moveA[i]];
		currA[0] += dy[moveA[i]];
		currB[1] += dx[moveB[i]];
		currB[0] += dy[moveB[i]];
		return;
	}
	

}