[SWEA 5644] 무선 충전

SWEA 5644 무선 충전

문제풀이

한 때 정말 어려운 문제라고 생각했던 무선 충전, 오늘 풀어보니 엄청 쉬운 문제였다... 그 때는 정말 생각의 힘이 부족했던 것 같다.

기본적인 구조는

• 주어진 시간만큼 진행한다.
  • 현재 위치에서 사용자 A, B가 충전한다.
  • 이동한다.

충전은 어떻게 할까? 중요한 것은 매 충전마다 둘의 충전량의 합이 최대가 되는 것이다. 따라서 간단하게 둘이 충전할 수 있는 모든 경우의 조합 중에 합이 최대가 되는 경우를 구하면 된다.

• 각 사용자의 위치에서 충전가능한 모든 BC를 각자의 List에 넣는다.
  • 두 List의 사이즈가 0이면 둘 다 충전을 못하므로 넘어간다.
  • 한 List의 사이즈가 0이면 다른 List의 최대 충전량을 구한다.
  • 둘다 사이즈가 0이 아니면
    • 이중 반복문으로 둘의 모든 조합을 구해서 최대 충전량을 구한다.

구현코드

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

public class Solution {
	
	static class Node {
		int x, y;
		
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	static int[][] bc;
	static int[][] user;
	static int[][] move;
	static int M, A, T, ans;
	static int[][] dir = {{0, 0}, {0, -1}, {1, 0}, {0, 1}, {-1, 0}};
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		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());
			ans = 0;
			
			bc = new int[A][4];
			user = new int[2][2];
			move = new int[2][M + 1];
			
			user[0][0] = 1;
			user[0][1] = 1;
			user[1][0] = 10;
			user[1][1] = 10;
			
			for(int i = 0 ; i < 2 ; ++i) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0 ; j < M ; ++j) {
					move[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int i = 0 ; i < A ; ++i) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0 ; j < 4 ; ++j) {
					bc[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int i = 0 ; i <= M ; ++i) {
				charge();
				user[0][0] += dir[move[0][i]][0];
				user[0][1] += dir[move[0][i]][1];
				user[1][0] += dir[move[1][i]][0];
				user[1][1] += dir[move[1][i]][1];
			}
			
			System.out.println("#" + t + " " + ans);
		}
	}

	private static void charge() {
		ArrayList<Integer> bcForA = new ArrayList<>();
		ArrayList<Integer> bcForB = new ArrayList<>();
		
		for(int i = 0 ; i < A ; ++i) {
			if(Math.abs(user[0][0] - bc[i][0]) + Math.abs(user[0][1] - bc[i][1]) <= bc[i][2]) {
				bcForA.add(i);
			}
			if(Math.abs(user[1][0] - bc[i][0]) + Math.abs(user[1][1] - bc[i][1]) <= bc[i][2]) {
				bcForB.add(i);
			}
		}

		int sizeA = bcForA.size();
		int sizeB = bcForB.size();
		int ap = 0, bp = 0;
		int max = 0;
		
		if(sizeA == 0 && sizeB == 0) {
			return;
		} else if(sizeA == 0) {
			for(int b : bcForB) {
				int sum = bc[b][3];
				bp = sum > bp ? sum : bp;
			}
		} else if(sizeB == 0) {
			for(int a : bcForA) {
				int sum = bc[a][3];
				ap = sum > ap ? sum : ap;
			}
		} else {
			for(int a : bcForA) {
				for(int b : bcForB) {
					int sum = 0;
					
					if(a == b) {
						sum = bc[a][3];
						
						if(sum > max) {
							ap = sum / 2;
							bp = sum / 2;
							max = sum;
						}
					} else {
						sum = bc[a][3] + bc[b][3];

						if(sum > max) {
							ap = bc[a][3];
							bp = bc[b][3];
							max = sum;
						}
					}
				}
			}
		}
		
		ans += ap + bp;
	}
}