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

모의 SW 역량테스트 무선충전

난이도 : 모의 SW 역량테스트
유형 : 구현

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

문제

스마트폰을 무선 충전 할 때 최적의 BC (Battery Charger)를 선택하는 알고리즘을 개발하고자 한다. [그림 1]과 같이 가로 세로 10*10 영역의 지도가 주어졌을 때, 설치된 BC 정보는 다음과 같다.

                                      [그림 1]

BC의 충전 범위가 C일 때, BC와 거리가 C 이하이면 BC에 접속할 수 있다. 이때, 두 지점 A(XA, YA), B(XB, YB) 사이의 거리는 다음과 같이 구할 수 있다.

D = |XA – XB| + |YA – YB|

위의 [그림 1]에서 (4,3)과 (5,4) 지점은 BC 1과 BC 3의 충전 범위에 모두 속하기 때문에, 이 위치에서는 두 BC 중 하나를 선택하여 접속할 수 있다.

                                      [그림 2]

[그림 2]와 같이 사용자 A와 B의 이동 궤적이 주어졌다고 가정하자. T는 초(Second)를 의미한다. 예를 들어 5초에 사용자 A는 (5, 2) 지점에, 사용자 B는 (6, 9) 지점에 위치한다.

매초마다 특정 BC의 충전 범위에 안에 들어오면 해당 BC에 접속이 가능하다. 따라서 T=5에 사용자 A는 BC 3에, 사용자 B는 BC 2에 접속할 수 있다. 이때, 접속한 BC의 성능(P)만큼 배터리를 충전 할 수 있다. 만약 한 BC에 두 명의 사용자가 접속한 경우, 접속한 사용자의 수만큼 충전 양을 균등하게 분배한다.

BC의 정보와 사용자의 이동 궤적이 주어졌을 때, 모든 사용자가 충전한 양의 합의 최댓값을 구하는 프로그램을 작성하라.

[그림 2]에서 T=11일 때, 사용자 A는 BC 1과 3 둘 중 하나에 접속이 가능하다. 같은 시간에 사용자 B는 BC 1에 접속할 수 밖에 없다. 따라서 사용자 A가 같은 BC 1에 접속한다면 충전되는 양를 반씩 나눠 갖게 되어 비효율적이다. 따라서 사용자 A가 BC 3에 접속하는 것이 더 이득이다.

위 예제에서 매 초마다 충전한 양은 다음과 같다. 따라서 총 충전한 양의 총합은 720 + 480 = 1200 이다.

제약사항

1. 지도의 가로, 세로 크기는 10이다.
2. 사용자는 총 2명이며, 사용자A는 지도의 (1, 1) 지점에서, 사용자B는 지도의 (10, 10) 지점에서 출발한다.
3. 총 이동 시간 M은 20이상 100이하의 정수이다. (20 ≤ M ≤ 100)
4. BC의 개수 A는 1이상 8이하의 정수이다. (1 ≤ A ≤ 8)
5. BC의 충전 범위 C는 1이상 4이하의 정수이다. (1 ≤ C ≤ 4)
6. BC의 성능 P는 10이상 500이하의 짝수이다. (10 ≤ P ≤ 500)
7. 사용자의 초기 위치(0초)부터 충전을 할 수 있다.
8. 같은 위치에 2개 이상의 BC가 설치된 경우는 없다. 그러나 사용자A, B가 동시에 같은 위치로 이동할 수는 있다. 사용자가 지도 밖으로 이동하는 경우는 없다.

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
테스트 케이스의 첫 번째 줄에는 총 이동 시간(M), BC의 개수(A)가 주어진다.
그 다음 2개의 줄에는 각각 사용자 A와 B의 이동 정보가 주어진다.
한 사용자의 이동 정보는 M개의 숫자로 구성되며, 각각의 숫자는 다음과 같이 매초마다 이동 방향을 의미한다.

출력

출력은 "#t"를 찍고 한 칸 띄운 다음 정답을 출력한다. (t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)
정답은 모든 사용자의 충전량 합의 최대값을 출력한다.

풀이

둘다 최대의 충전이 겹칠 때가 문제였다.
해결방안은 A,B가 이동할때마다 해당 좌표에서 충전할 수 있는 충전기를 모두 각각의 리스트에 추가해준다음, 리스트 2중 for문을 돌면서 최대의 충전파워에서 / 2한게 더 좋은지, 한명이 양보해서 최대에서 2번째 충전을 쓰면서 한명은 최대충전, 양보한 한명은 2번째파워충전을 하는지 더 좋은지를 비교할 수 있게 된다.

정말 복잡한문제다. 문제도 길고 고려해야할 사안이 만만치않다..

코드

/**
 * SWEA_5644_무선충전
 * @author mingggkeee
 * 구현
 */ 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class SWEA_5644 {

	static class BC {
		int x;
		int y;
		int c;
		int p;
				
		public BC(int x, int y, int c, int p) {
			this.x = x;
			this.y = y;
			this.c = c;
			this.p = p;
		}
	}
	
	static int chargeMax;
	static int M, A, x1, y1, x2, y2;
	static int[] moveA, moveB;
	static BC[] list;
	static int[][] dir = {{0,0}, {0,-1}, {1,0}, {0,1}, {-1,0}};
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	
	public static void main(String[] args) throws IOException {
		
		int T = Integer.parseInt(br.readLine());
		input(T);
	}
	
	// 입력
	public static void input(int T) throws IOException{
		for(int tc=1; tc<=T; tc++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			M = Integer.parseInt(st.nextToken());
			A = Integer.parseInt(st.nextToken());
			moveA = new int[M];
			moveB = new int[M];
			list = new BC[A];
			
			// A 무빙 입력
			st = new StringTokenizer(br.readLine(), " ");
			for(int i=0; i<M; i++) {
				moveA[i] = Integer.parseInt(st.nextToken());
			}
			// B 무빙 입력
			st = new StringTokenizer(br.readLine(), " ");
			for(int i=0; i<M; i++) {
				moveB[i] = Integer.parseInt(st.nextToken());
			}
			
			// 충전기 정보 입력
			for(int i=0; i<A; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				list[i] = new BC(
							Integer.parseInt(st.nextToken()),
							Integer.parseInt(st.nextToken()),
							Integer.parseInt(st.nextToken()),
							Integer.parseInt(st.nextToken())							
						);
			}
			
			chargeMax = 0;
			x1=y1=1;
			x2=y2=10;
			// 0부터 시작이니까 계산먼저		
			for(int i=0; i<M; i++) {
				chargeMax += calculator();
				x1 += dir[moveA[i]][0];
				y1 += dir[moveA[i]][1];
				x2 += dir[moveB[i]][0];
				y2 += dir[moveB[i]][1];
			}
			// 마지막 정보까지
			chargeMax += calculator();
			
			System.out.println("#" + tc + " " + chargeMax);
		}
	}
	
	public static int calculator() {
		
		ArrayList<BC> A = new ArrayList<>();
		ArrayList<BC> B = new ArrayList<>();
		
		for(int i=0; i<list.length; i++) {
			BC bc = list[i];
			
			int lengthA = Math.abs(x1-bc.x) + Math.abs(y1-bc.y);
			int lengthB = Math.abs(x2-bc.x) + Math.abs(y2-bc.y);
			
			
			if(lengthA <= bc.c) {
				A.add(bc);
			}
			
			if(lengthB <= bc.c) {
				B.add(bc);
			}
		}
		
		
		int temp = 0;
		
		// A만 범위안에 있을 때
		if(B.size() == 0) {
			for(BC bc : A) {
				temp = Math.max(bc.p, temp);
			}
		} else if(A.size() == 0) {
			// B만 범위안에 있을 때
			for(BC bc : B) {
				temp = Math.max(bc.p, temp);
			}
		} else if (A.size() != 0 && B.size() != 0) {
			// A B 둘다 범위 안에 있을 떄
			for(BC bcA : A) {
				for(BC bcB : B) {
					if((bcA.x == bcB.x) && (bcA.y == bcB.y)) {
						temp = Math.max(temp, bcA.p);
					} else {
						temp = Math.max(temp, bcA.p+bcB.p);
					}
				}
			}
		}
		
		return temp;
	}
	
}