[SWEA] 5644. [모의 SW 역량테스트] 무선 충전 Java

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

SW Expert Academy

---

1. 문제요약

A는 (1,1) B는 (10,10) 좌표에서 시작하여 매 초마다 이동하면서, 해당 좌표가 충전 범위에 있을 경우 두 사용자가 충전한 값의 최댓값을 구해 누적합을 구하는 문제이다.

두 사용자의 좌표가 같은 충전기의 범위 안에 있을 경우, 충전기의 충전량/2씩 충전된다. 즉, 총 충전량은 해당 충전기의 충전량과 같다.

2. 풀이

1. 두 사용자의 시작위치에서부터 충전범위를 체크한다.

2. 매 초마다 두 사용자의 좌표를 이동시키고, 각각의 좌표에서 충전범위를 체크한다. 

1. 해당 좌표에서 충전 가능한 충전기 번호를 각각의 List에 저장한다.
   (충전기 번호 당 범위 >= 충전기와 좌표의 거리)
   (여러 충전기의 범위에 해당되는 경우 여러개가 담긴다.)     

• 두 사용자 모두 충전 범위에 있을 경우 : 모든 조합을 본다.
  => 충전기 번호가 같으면 충전기 충전량, 다르면 두 충전기 충전량 합
  => 조합마다 최대값 구함
• A사용자만 충전 범위에 있을 경우 : ListA에 담긴 충전기 충전량 최대값
• B사용자만 충전 범위에 있을 경우 : ListB에 담긴 충전기 충전량 최대값

3. 해당 초의 최대값이 나오면 누적하여 더한다. (결과값 = 최대값의 누적합)

3. 코드

import java.util.*;
import java.io.*;

public class SW_5644_무선충전 {

	static int M, A, res;
	static int[] dirA, dirB;
	static BC[] BC;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			A = Integer.parseInt(st.nextToken());
			
			dirA = new int[M];
			dirB = new int[M];
			BC = new BC[A];
			res = 0;
			
			//1. A이동 정보 저장
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < M; m++) {
				dirA[m] = Integer.parseInt(st.nextToken());
			}
			//2. B이동 정보 저장
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < M; m++) {
				dirB[m] = Integer.parseInt(st.nextToken());
			}
			
			//3. BC정보 저장
			for (int a = 0; a < A; a++) {
				st = new StringTokenizer(br.readLine());
				BC[a] = new BC(new Point( Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) ),
						Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			} //입력 끝
			
			solution();
			
			System.out.println("#"+t+" "+res);
		}
	}

	static void solution() {
		//1. 초기 좌표 - 충전 max 찾기
		Point userA = new Point(1,1);
		Point userB = new Point(10,10);
		charge(userA, userB);
		
		//2. 움직임 - 충전 max 찾기
		for (int i = 0; i < M; i++) {
			move(userA, dirA[i]);
			move(userB, dirB[i]);
			charge(userA, userB);
		}
	}
	
	//그 초마다 최대값을 더하고 가는거임
	static void charge(Point userA, Point userB) {
		//A와 B 위치의 접속 가능한 BC리스트
		List<Integer> ListA = new ArrayList<> ();
		List<Integer> ListB = new ArrayList<> ();
		
		//BC개수만큼 반복
		for (int i = 0; i < A; i++) {
			//A좌표가 각각 BC 범위 안에있는지 - 있으면 리스트에 add
			if (BC[i].c >= Math.abs( BC[i].point.x - userA.x ) + Math.abs( BC[i].point.y - userA.y ) ) {
				ListA.add(i);
			}
			//B좌표가 각각 BC 범위 안에있는지 - 있으면 리스트에 add
			if (BC[i].c >= Math.abs( BC[i].point.x - userB.x ) + Math.abs( BC[i].point.y - userB.y ) ) {
				ListB.add(i);
			}
		}
		
		int max = 0, tmp = 0;
		
		//1. A,B 모두 list에 1개 이상일 때
		if ( ListA.size() >= 1 && ListB.size() >= 1 ) {
			//모든 조합을 봄
			for (int i : ListA) {
				for (int j : ListB) {
					tmp = 0;
					if (i == j) {
						tmp = BC[i].p;
					} else {
						tmp = (BC[i].p + BC[j].p);
					}
					max = Math.max( max, tmp );
				}
			}
		}
		//2. A list에만 1개 이상일 때 (B는 BC들의 범위에 없을 때)
		else if ( ListA.size() >= 1 && ListB.size() == 0 ) {
			for (int i : ListA) {
				max = Math.max( max, BC[i].p );
			}
		}
		//3. B list에만 1개 이상일 때 (A는 BC들의 범위에 없을 때)
		else if ( ListA.size() == 0 && ListB.size() >= 1 ) {
			for (int i : ListB) {
				max = Math.max( max, BC[i].p );
			}
		}
		res += max;
	}
	

	static void move(Point point, int dir) {
		int[] dy = {0,-1,0,1,0};
		int[] dx = {0,0,1,0,-1};
		//좌표 이동
		point.y += dy[dir];
		point.x += dx[dir];
	}
	
	static class BC {
		Point point;
		int c, p;
		public BC(Point point, int c, int p) {
			this.point = point;
			this.c = c;
			this.p = p;
		}
	}
	
	static class Point {
		int y, x;
		public Point(int x, int y) {
			this.y = y;
			this.x = x;
		}
	}
}