문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo
경우의 수 나누는 훈련을 하고 있는거 같다 (…)
– 0 (처음에 안 움직일 때)~ M (주어진 시간)까지 해서 M+1번 정보를 업데이트 해야됨.
– 0일 때 빼고는 이동 정보를 업데이트하고, 이후 사람A과 B가 접근할 수 있는 BC들의 목록을 정함
– 둘 다 접근할 수 있는 BC가 1개 이상이면 겹칠 가능성이 있으므로 모든 경우의 수를 계산하고, 한 명이라도 접근할 수 있는 BC가 0개인 경우 겹칠 일이 없으므로 파워가 가장 센 BC 선택
import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) throws IOException { //System.setIn(new FileInputStream("./src/sample_input.txt")); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); try { int numCases = Integer.parseInt(reader.readLine()); for (int num = 0; num < numCases; num++) { writer.write("#" + String.valueOf(num + 1) + " "); // 기본 A, B 위치 int xUserA = 1, yUserA = 1; int xUserB = 10, yUserB = 10; String[] tmp = reader.readLine().split(" "); int numM = Integer.parseInt(tmp[0]); // 총 이동 시간 int numA = Integer.parseInt(tmp[1]); // BC의 갯수 // 사용자 A 이동 정보 (0: 이동 안함, 1: 상, 2: 우, 3: 하, 4: 좌) String[] tmp_ = reader.readLine().split(" "); int[] userA = new int[tmp_.length]; // 사용자 A의 이동 정보 for (int i = 0; i < tmp_.length; i++) userA[i] = Integer.parseInt(tmp_[i]); // 사용자 B 이동 정보 (0: 이동 안함, 1: 상, 2: 우, 3: 하, 4: 좌) tmp_ = reader.readLine().split(" "); int[] userB = new int[tmp_.length]; // 사용자 B의 이동 정보 for (int i = 0; i < tmp_.length; i++) userB[i] = Integer.parseInt(tmp_[i]); // BC 정보 int[] xBC = new int[numA]; // 좌표 (X) int[] yBC = new int[numA]; // 좌표 (Y) int[] cBC = new int[numA]; // 충전 범위 int[] pBC = new int[numA]; // 처리량 for (int i = 0; i < numA; i++) { String[] tmp__ = reader.readLine().split(" "); xBC[i] = Integer.parseInt(tmp__[0]); yBC[i] = Integer.parseInt(tmp__[1]); cBC[i] = Integer.parseInt(tmp__[2]); pBC[i] = Integer.parseInt(tmp__[3]); } // 실제 최대 충전량 계산 int answer = 0; // -1: 움직이기 전, 0~numM-1: 움직이는 중 (0~numM 을 -1~numM-1 로 환산) for (int i = -1; i < numM; i++) { // // 움직이는 경우 (i == -1이면 이동할 필요가 없음) if (i != -1) { switch (userA[i]) { case 1: // 상 yUserA--; break; case 2: // 우 xUserA++; break; case 3: // 하 yUserA++; break; case 4: // 좌 xUserA--; break; } switch (userB[i]) { case 1: // 상 yUserB--; break; case 2: // 우 xUserB++; break; case 3: // 하 yUserB++; break; case 4: // 좌 xUserB--; break; } } // 해당 시간에 사용자 A, B가 도달 가능한 BC 목록 List<Integer> BCForUserA = new ArrayList<Integer>(); List<Integer> BCForUserB = new ArrayList<Integer>(); for (int j = 0; j < numA; j++) { int distanceA = Math.abs(xUserA - xBC[j]) + Math.abs(yUserA - yBC[j]); int distanceB = Math.abs(xUserB - xBC[j]) + Math.abs(yUserB - yBC[j]); if (distanceA <= cBC[j]) BCForUserA.add(j); if (distanceB <= cBC[j]) BCForUserB.add(j); } // 각 시간 별 최대값 구함 int maxValue = 0; if (BCForUserA.size() >= 1 && BCForUserB.size() >= 1) { // 둘 다 경우의 수가 1 이상이면 비교 필요 for (int caseA: BCForUserA) { for (int caseB: BCForUserB) { if (caseA == caseB) { // 같은 경우 절반씩 나눠가짐 if (maxValue < 0.5 * (pBC[caseA] + pBC[caseB])) maxValue = (int) (0.5 * (pBC[caseA] + pBC[caseB])); } else { // 다른 경우 각자의 최대값 적용 if (maxValue < pBC[caseA] + pBC[caseB]) maxValue = pBC[caseA] + pBC[caseB]; } } } } else { // 둘 중 한 쪽 이상이 size() == 0이면 한쪽만 계산 if (BCForUserA.size() == 0 && BCForUserB.size() == 0) // 둘 다 0 continue; else if (BCForUserA.size() == 0) { // B만 경우의 수가 있음 for (int caseB: BCForUserB) { if (maxValue < pBC[caseB]) maxValue = pBC[caseB]; } } else if (BCForUserB.size() == 0) { // A만 경우의 수가 있음 for (int caseA: BCForUserA) { if (maxValue < pBC[caseA]) maxValue = pBC[caseA]; } } } answer += maxValue; } writer.write(answer + System.lineSeparator()); writer.flush(); } } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } }