[SWEA/구현] 무선 충전 [모의 SW 역량테스트] - 자바

문제

---

문제링크

SW Expert Academy

 

풀이

---

구현 문제이다.

두 유저가 이동할 때 사용할 수 있는 충전기 범위에 있다면 충전할 수 있는데

시간이 전부 흐르고 나서 두 유저가 최대로 충전할 수 있는 충전량을 구하는 문제다.

 

분기점은 다음과 같다. 

1. 두 유저가 충전 범위에 있을 때
   • 두 유저가 사용할 수 있는 파워가 가장 큰 충전기가 같을 때 
     • 두 유저가 사용할 수 있는 충전기가 둘다 1개일 때  -> 한 유저가 충전기 사용을 포기하고 다른 유저가 사용
     • 한 유저가(혹은 두 유저가) 사용할 수 있는 충전기가 2개일 때 -> 두개를 가지고 있는 유저가 파워가 큰 첫번째 충전기 사용을 양보하고 충전기를 1개 사용할 수 있는 유저가 사용함.
2. 한 유저가 충전 범위에 있을 때
   • 해당 유저가 사용할 수 있는 충전값 계산
3. 두 유저가 충전 범위에 없을 때
   • 충전값 계산하지 않음.

이를 토대로 구현해 보았다. 코드에 대한 설명은 주석을 참조하면 되겠다.

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

public class SWEA_5644 {
	static StringTokenizer st;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int M, A;
	static int[] personA, personB;
	static int[][] dire = new int[][] {{0,0},{0,-1},{1,0},{0,1},{-1,0}}; // 상-> 우-> 하-> 좌
	static int Ax, Ay, Bx, By; // A, B 사람 좌표
	static List<BC> bcList; // 충전기 리스트
	static int ans; 
	
	static class BC implements Comparable<BC>{
		int x,y,coverage,power;

		public BC(int x, int y, int coverage, int power) {
			super();
			this.x = x;
			this.y = y;
			this.coverage = coverage;
			this.power = power;
		}

		@Override
		public int compareTo(BC o) { // BC클래스를 power순으로 오름차순 정렬
			return o.power - this.power;
		}
		
// 유저가 있는 위치로부터 해당 충전기 범위에 들어오는지 확인
		public boolean isCoverage(int userX, int userY) { 
			return (Math.abs(this.x - userX) + Math.abs(this.y - userY)) <= coverage;
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			ans = 0;
			inputData();
			flowTime();
			System.out.printf("#%d %d\n", tc, ans);
		}
	}
	
// 입력
	public static void inputData() throws IOException {

		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		A = Integer.parseInt(st.nextToken());

		personA = new int[M];
		personB = new int[M];

//사용자 A, B가 이동할 방향을 넣음
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) personA[i] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) personB[i] = Integer.parseInt(st.nextToken());

		bcList = new ArrayList<>();

// 충전기 리스트에 X좌표 Y좌표 범위, 파워를 리스트에 저장함
		for (int i = 0; i < A; i++) {
			st = new StringTokenizer(br.readLine());
			int inputX = Integer.parseInt(st.nextToken());
			int inputY = Integer.parseInt(st.nextToken());
			int inputCoverage = Integer.parseInt(st.nextToken());
			int inputPower = Integer.parseInt(st.nextToken());
			bcList.add(new BC(inputX-1, inputY-1, inputCoverage, inputPower));
		}
		Collections.sort(bcList); // 파워순으로 무선충전기 정렬
	}
	
	public static void init() { Ax = 0;Ay = 0;Bx = 9;By = 9; }
	
	public static void flowTime() {
		init();
		
		for(int time = 0; time <= M; time++) {
			int max = 0;
	
			ArrayList<Integer> enableA = new ArrayList<>();
			ArrayList<Integer> enableB = new ArrayList<>();
			
			// 현재 시간에서 사용자가 위치한 곳에 충전기가 있는지 확인
			// 있으면 리스트에 저장
			for(int i = 0; i < A; i++) {
				BC bc = bcList.get(i);
				if(bc.isCoverage(Ax, Ay)) enableA.add(i);
				if(bc.isCoverage(Bx, By)) enableB.add(i);
			}
			
			// 두 유저 위치에서 사용할 수 있는 충전기가 어느 한 유저라도 있다면
			if(!enableA.isEmpty() || !enableB.isEmpty()) {
				// 두 유저 위치에서 사용할 수 있는 충전기가 두 유저 둘 다 있을 때 
				if(!enableA.isEmpty() && !enableB.isEmpty()) {
					// 두 유저 위치에서 사용할 수 있는 충전기가 같을 때
					if(enableA.get(0) == enableB.get(0)) {
						if(enableA.size() >= 2) { // A유저가 사용할 수 있는 충전기가 2개 이상이라면
							// A유저는 두번째로 파워가 큰 충전기 사용 B는 첫번째로 파워가 큰 충전기 사용
							int Apower = bcList.get(enableA.get(1)).power;
							int Bpower = bcList.get(enableB.get(0)).power;
							max = Math.max(Apower+Bpower, max);
						}
						if(enableB.size() >= 2) { // B유저가 사용할 수 있는 충전기가 2개 이상이라면
						 // A유저는 두번째로 파워가 큰 충전기 사용 B는 첫번째로 파워가 큰 충전기 사용
							int Apower = bcList.get(enableA.get(0)).power;
							int Bpower = bcList.get(enableB.get(1)).power;
							max = Math.max(Apower+Bpower, max);
						}
					}
						// 두 유저 위치에서 사용할 수 있는 충전기가 서로 다를 때
					else {
						int Apower = bcList.get(enableA.get(0)).power;
						int Bpower = bcList.get(enableB.get(0)).power;
						max = Math.max((Apower+Bpower), max);
					}
				}
				// 위의 조건들을 만족하지 않는 = 한 유저만 충전기 범위에 있을 때
				if(!enableA.isEmpty()) max = Math.max(bcList.get(enableA.get(0)).power, max);
				if(!enableB.isEmpty()) max = Math.max(bcList.get(enableB.get(0)).power, max);
				ans += max;
			} 
			if(time == M) continue;
			int aIdx = personA[time];
			int bIdx = personB[time];
			Ax += dire[aIdx][0];
			Ay += dire[aIdx][1];
			Bx += dire[bIdx][0];
			By += dire[bIdx][1];
		}
	}
}

 

다른 풀이

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

public class SWEA_5644_refactoring {

	static class User {
		int r, c;

		public User(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static class BC {
		int r, c, coverage, performance;

		public BC(int r, int c, int coverage, int performance) {
			this.r = r;
			this.c = c;
			this.coverage = coverage;
			this.performance = performance;
		}

	}

	static int M, A;
	static User aUser, bUser;
	static BC[] bc;
	static int[] dr = { 0, -1, 0, 1, 0 };
	static int[] dc = { 0, 0, 1, 0, -1 };
	static int[] aPath, bPath; // a사용자경로, b사용자 경로

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken()); // 총 이동시간
			A = Integer.parseInt(st.nextToken()); // BC갯수

			aPath = new int[M + 1];
			bPath = new int[M + 1];

			// a사용자에 대한 경로, b사용자에 대한 경로
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++)
				aPath[i] = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++)
				bPath[i] = Integer.parseInt(st.nextToken());

			bc = new BC[A];
			for (int i = 0; i < A; i++) {
				st = new StringTokenizer(br.readLine());
				int inputX = Integer.parseInt(st.nextToken());
				int inputY = Integer.parseInt(st.nextToken());
				int inputCoverage = Integer.parseInt(st.nextToken());
				int inputPerformance = Integer.parseInt(st.nextToken());
				bc[i] = new BC(inputX, inputY, inputCoverage, inputPerformance);
			}

			aUser = new User(1, 1);
			bUser = new User(10, 10);

			System.out.println("#" + t + " " + solve());
		}
	}

	private static int solve() {
		int ans = 0;
		for (int time = 0; time <= M; time++) { // 각 시간별 모든 충전소에 접근해서 가장 큰 값을 얻는다.
			// 사용자의 위치 이동(aUser, bUser)
			aUser.r += dr[aPath[time]];
			aUser.c += dc[aPath[time]];
			bUser.r += dr[bPath[time]];
			bUser.c += dc[bPath[time]];

			ans += getCharge(); // 최대 충전량 계산
		}
		return ans;
	}

	private static int getCharge() {
		int max = 0;
		for (int a = 0; a < A; a++) { // a유저 선택 BC
			for (int b = 0; b < A; b++) { // b유저 선택 BC
				int sum = 0;
				int aSum = getBCPerformance(a, aUser);
				int bSum = getBCPerformance(b, bUser);
				if (a != b)
					sum = aSum + bSum;
				else
					sum = Math.max(aSum, bSum);

				if (max < sum)
					max = sum;

			}
		}
		return 0;
	}

	// 배터리의 위치와 사용자의 위치를 계산하여 범위에 들어오는지 확인.
	private static int getBCPerformance(int idx, User user) {
		return (Math.abs(bc[idx].r - user.r) + Math.abs(bc[idx].c - user.c) <= bc[idx].coverage) 
				? bc[idx].performance : 0;
	}
}