[Java] SWEA / 무선 충전 / 5644번

[Java] SWEA / 무선 충전 / 5644번

문제

무선 충전 문제 링크

문제의 저작권은 SW Expert Academy에 있습니다

입력

1
20 3
2 2 3 2 2 2 2 3 3 4 4 3 2 2 3 3 3 2 2 3
4 4 1 4 4 1 4 4 1 1 1 4 1 4 3 3 3 3 3 3
4 4 1 100
7 10 3 40
6 3 2 70

출력

#1 1200

접근 방식

1. 각 초마다 사용자 A, B 가 BC의 충전범위 내에 있는지 확인 한다
2. A,B 둘다 BC 의 충전 범위내에 없다면 다음 초로 넘어간다
3. A,B 둘중 한명만 충전 범위 내에 있다면 해당 BC 중 가장 처리량이 큰 값을 저장한다
4. A와 B 둘다 충전 범위 내에 있다면 조합을 통해 A와 B가 포함되어있는 BC를 선택할 모든 경우의 수를 탐색하며 처리량이 가장 큰 값을 저장한다

코드

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

public class Solution_5644_정현명 {

	static int T,M,A;
	static int[] userA, userB;
	static int[][] infoBC;
	static int userA_R,userA_C,userB_R,userB_C;
	static int[][] deltas = {{0,0},{-1,0},{0,1},{1,0},{0,-1}};
	static int sum;
	public static void main(String[] args) throws IOException{
		
		// =============================== 입력 ==================================
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		T = Integer.parseInt(br.readLine()); // 테스트케이스
		
		for(int tc=1;tc<=T;tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			
			M = Integer.parseInt(st.nextToken()); // 시간 초 
			A = Integer.parseInt(st.nextToken()); // BC 개수
			
			StringTokenizer stA = new StringTokenizer(br.readLine());
			StringTokenizer stB = new StringTokenizer(br.readLine());
			
			userA = new int[M+1]; // 사용자 A의 방향정보
			userB = new int[M+1]; // 사용자 B의 방향정보
			
			
			for(int i=1;i<=M;i++) {
				userA[i] = Integer.parseInt(stA.nextToken());
				userB[i] = Integer.parseInt(stB.nextToken());
			}
			
			infoBC = new int[A][4]; // BC 정보
			
			for(int i=0;i<A;i++) {
				StringTokenizer stAP = new StringTokenizer(br.readLine());
				for(int j=0;j<4;j++) {
					infoBC[i][j] = Integer.parseInt(stAP.nextToken());
				}
			}
			
			// 위치 초기화
			userA_R = 1;
			userA_C = 1;
			userB_R = 10;
			userB_C = 10;
			
			// 충전량 합 초기화
			sum = 0;
			
			// solution
			cal();
			
			sb.append("#"+tc+" "+sum+"\n");
		}
		System.out.println(sb);
	}
	
	public static void cal() {
		// 0초부터 M초까지 ( 0초에는 이동하지 않음을 넣어 deltas를 더해줘서 시작 위치를 고려 )
		for(int i=0;i<=M;i++) {
			
			userA_R += deltas[userA[i]][0];
			userA_C += deltas[userA[i]][1];
			userB_R += deltas[userB[i]][0];
			userB_C += deltas[userB[i]][1];
			
			// user A 와 user B 가 각각 BC의 충전범위 내에 들어왔는지 확인
			boolean[] userAinBC= new boolean[A];
			boolean[] userBinBC= new boolean[A];
			
			// 어떤 BC 충전범위 이내에도 들어오지 못한 경우 true
			boolean isNoChargeA = true;
			boolean isNoChargeB = true;
			
			
			for(int j=0;j<A;j++) {
				int bcR = infoBC[j][1];
				int bcC = infoBC[j][0];
				int bcRange = infoBC[j][2];
				
				if(Math.abs(bcR - userA_R) + Math.abs(bcC - userA_C) <= bcRange) {
					userAinBC[j] = true;
					isNoChargeA = false;
				}
				if(Math.abs(bcR - userB_R) + Math.abs(bcC - userB_C) <= bcRange) {
					userBinBC[j] = true;
					isNoChargeB = false;
				}
			}
			
			// BC들의 충전범위에 아무도 들어오지 못한 경우
			if(isNoChargeA && isNoChargeB) continue;
			
			// 둘중 한명만 BC들의 충전 범위 내에 들어온 경우
			else if((isNoChargeA && !isNoChargeB) || (!isNoChargeA && isNoChargeB)) {
				int sub = 0;
				for(int j=0;j<A;j++) {
					if(userAinBC[j] || userBinBC[j]) {
						sub = Math.max(sub, infoBC[j][3]);
					}
				}
				sum+= sub;
			}
			
			// 둘 다 BC들의 충전 범위 내에 들어온 경우 
			else {
				int sub = 0;
				for(int j=0;j<A;j++) {
					for(int k=0;k<A;k++) {
						if(userAinBC[j] && userBinBC[k]) {
							if(j == k) sub = Math.max(sub, infoBC[j][3]);
							else {
								sub = Math.max(sub, infoBC[j][3] + infoBC[k][3]);
							}
						}
					}
				}
				
				sum += sub;
			}
			
		}
	}

}