/ SWEA

SWEA_5644_무선충전_JAVA

문제 : 무선충전

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_5644_무선충전

접근 방식

IM 모의 문제라서 그런지, 문제가 상당히 복잡했다.

요점은 이렇다.

  1. 10*10의 2차원 평면이 있고, A와 B는 그 양쪽 대각선 끝에서 출발한다.

  2. 평면에는 BC라는 무선충전기가 배치되어있는데, 일정 거리 안에 있어야만 충전이 가능하다.

  3. BC는 1초에 P만큼 스마트폰을 충전시킬 수 있다. 만약 BC의 주변에 2대의 스마트폰이 있다면, P의 충전량을 균등하게 분배한다.

  4. A,B가 정해진 루트로 이동을 할 때, 모든 사용자가 최대로 충전할 수 있는 충전량을 구하라.

풀이 방법

나는, 이 무선충전의 해를 구하기 위해 먼저 객체를 생성하기 위한 클래스를 만들었다.

Human클래스는 A,B의 좌표정보를 저장하기 위한 클래스이다. 추가로 isEnergy라는 boolean배열을 선언했는데, 이는 현재 위치에서 접속 가능한 BC의 정보를 담을 배열이다.

BC클래스는 BC 객체를 생성하기 위한 클래스이다. BC는 각각 X,Y좌표, 충전가능한 거리 C, 1초에 충전가능한 충전량 P를 멤버변수로 가진다.

이렇게 클래스를 만들어 두고, 메인 메서드로 넘어가는데, 기본적으로 Input 파일의 입력 설명대로 값을 읽어와서 저장을 했다.

A,B정보는 Human객체를 생성하여 저장했고, BC는 BC의 List를 선언해서 생성해주었다.

그 후, A와 B의 현재 위치(초기위치)에서 충전가능한지 여부를 확인한다. 확인 방법은 다음과 같다. A를 기준으로 설명하겠다.

BC리스트에 저장된 모든 BC와 A와의 거리를 비교하여, A가 BC의 충전가능 범위에 있는지 확인한다. 만약 충전가능 범위에 있다면 A에 선언해두었던 isEnergy배열의 해당 위치 값을 true로 바꾼다. 반대로 충전가능 범위에 없다면, isEnergy 배열의 해당 위치 값을 false로 바꿔준다.

초기 위치에서 충전가능한지 여부 확인을 마쳤다면, 이제 현재 자리에서 가능한 최대 충전량을 구해야한다.

A를 기준으로 BC를 탐색하며 충전가능한 최댓값을 구한다. A와 B가 겹치는 경우와, A와 B가 겹치지 않는 경우를 모두 상정해야하는 점에 주의한다.

구해진 초기 max값을 정답을 출력하기 위한 변수 answer에 할당해 초기화해준다.

위 과정을 A,B를 주어진 루트만큼 이동시키며 반복한다. 초기 1회를 먼저 돌리는 이유는 0초부터 충전이 가능하다는 규칙을 따르기 위해서이다. 1번 반복될때마다 answer에 max값을 sum해준다.

모든 반복이 종료된 후 answer를 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class 모의_5644_무선충전 {
	// 총 충전량 저장 변수
	static int answer;
	// 매회 최대 충전량 저장 변수
	static int max;


	public static void max(Human A, Human B, List<BC> bcQ) {
		// 충전 가능 여부 비교하여 현재 저장 가능한 최댓값 저장
		int energyA = 0;
		int U = A.isEnergy.length;
		for (int i = 0; i < U; i++) {
			// AC별 충전량 저장 변수
			int energyB = 0;
			// A가 i번째 BC에서 충전가능하면
			if (A.isEnergy[i] == true) {
				// B도 같은 BC에 대해 충전 가능한지 확인
				// A, B가 같은 BC에 접속 가능한 경우
				if (B.isEnergy[i] == true) {
					energyA = bcQ.get(i).P / 2;
					energyB = energyA;
					max = Math.max(max, energyA+energyB);
				}
				energyA = 0;
				energyB = 0;
				// A와 B가 다른 BC에 접속 가능한 경우
				for (int j = 0; j < U; j++) {
					// 가능한 에너지 값중에 최댓값
					if (j != i && B.isEnergy[j] == true) {
						energyB = Math.max(bcQ.get(j).P,energyB);
					}

					energyA = bcQ.get(i).P;
					max = Math.max(max, energyA+energyB);
				}
			}else { // A가 i번째 BC에서 충전 불가능하면
				energyA = 0;
				for (int j = 0; j < U; j++) {
					// 가능한 에너지 값중에 최댓값
					if (B.isEnergy[j] == true) {
						energyB = Math.max(bcQ.get(j).P,energyB);
					}
				}
				max = Math.max(max, energyA+energyB);
			}

		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {

		System.setIn(new FileInputStream("input_5644.txt"));

		// 버퍼드리더로 값 읽어오기
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		// 테케
		int T = Integer.parseInt(in.readLine());

		// X,Y좌표 바꿨기 때문에, 방향정보도 바뀔 필요가 있다.
		// 0:제자리, 1: 좌, 2: 하 3: 우 4: 상
		int[][] dir = { { 0, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };

		// 테케만큼 반복
		for (int tc = 1; tc <= T; tc++) {
			// StringTokenizer로 값 읽어오기, 2번째 줄 저장
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");

			// 이동시간
			int M = Integer.parseInt(st.nextToken());

			// BC 개수 U로 네이밍 변경
			int U = Integer.parseInt(st.nextToken());

			// A, B 초기 위치 저장
			Human A = new Human(1, 1);
			Human B = new Human(10, 10);

			int[] moveA = new int[M];
			int[] moveB = new int[M];
			// A 이동 정보 저장
			st = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < M; i++) {
				moveA[i] = Integer.parseInt(st.nextToken());
			}
			// B 이동 정보 저장
			st = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < M; i++) {
				moveB[i] = Integer.parseInt(st.nextToken());
			}

			// BC 목록 저장
			List<BC> bcQ = new ArrayList<>();

			// BC 할당
			for (int i = 0; i < U; i++) {
				// BC정보 읽어오기
				st = new StringTokenizer(in.readLine(), " ");
				int y = Integer.parseInt(st.nextToken());
				int x = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				int p = Integer.parseInt(st.nextToken());
				// 한줄에다 다 적을 수 있지만 보기싫어서 나눔
				bcQ.add(new BC(y, x, c, p));
			}

			// A, B의 충전가능여부 저장할 배열
			A.isEnergy = new boolean[U];
			B.isEnergy = new boolean[U];

			// 현재 위치에서 충전가능한지 먼저 확인
			isEnegy(A, bcQ);
			isEnegy(B, bcQ);
////			 테스트, 여기까지는 잘됨
//			System.out.println(Arrays.toString(A.isEnergy));
//			System.out.println(Arrays.toString(B.isEnergy));

			// 매회 최대 충전량 저장 변수 초기화
			max = 0;

			// 현재 자리에서 가능한 최대 충전량 구하기
			max(A, B, bcQ);

			// 총 충전량 저장 변수 초기화
			answer = max;
			// 여기까지 잘 됨
//			System.out.println(answer);

			// 이동 시간만큼 반복
			for (int i = 0; i < M; i++) {
				max = 0;
				// A 이동
				A.X = A.X + dir[moveA[i]][0];
				A.Y = A.Y + dir[moveA[i]][1];
//				System.out.println("T:"+i+" A:"+A.X+","+A.Y);
				// B 이동
				B.X = B.X + dir[moveB[i]][0];
				B.Y = B.Y + dir[moveB[i]][1];
//				System.out.println("T:"+i+" B:"+B.X+","+B.Y);

				// 현재 위치에서 충전 가능한지 여부 확인
				isEnegy(A, bcQ);
				isEnegy(B, bcQ);
//				System.out.println(Arrays.toString(A.isEnergy));
//				System.out.println(Arrays.toString(B.isEnergy));
				// 현재 위치에서 가능한 충전량의 최댓값 구하기
				max(A,B,bcQ);
//				System.out.println("Max: "+ max);
				// 해당 최댓값 총 충전량에 더하기
				answer += max;
			}
			// ---- 출력
			System.out.printf("#%d %d\n",tc,answer);
		}

	}

	public static void isEnegy(Human human, List<BC> bcQ) {
		for (int i = 0, n = bcQ.size(); i < n; i++) {
			// A와 BC간의 거리 비교하여 충전 가능한 BC에대해 boolean값 저장
			if ((Math.abs(human.X - bcQ.get(i).X) + Math.abs(human.Y - bcQ.get(i).Y)) <= bcQ.get(i).C) {
				human.isEnergy[i] = true;
			}else {
				human.isEnergy[i] = false;
			}
		}

	}

}

class Human {
	int X;
	int Y;
	boolean[] isEnergy;

	public Human(int x, int y) {
		super();
		X = x;
		Y = y;
	}
}

class BC {
	// x좌표
	int X;
	// y좌표
	int Y;
	// 충전범위 - 구할 수 있으니까 스킵?
	int C;
	// 성능
	int P;

	public BC(int x, int y, int c, int p) {
		super();
		X = x;
		Y = y;
		C = c;
		P = p;
	}

}