SWEA 2117번
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo
문제
생각하기
- 부르트 포스 문제이다.
- 유저 2명이 AP가 겹치는 경우가 있을 때, 어떤 조합이 가장 높은 충전값을 가지는 지 모든 경우의 수를 계산해 봐야하기 때문
-
거리를 계산하면 되기 때문에 딱히 어렵지 않은 문제.
-
해당 문제에서 AP의 좌표
xy가 반대로 되어 있으니 주의해야됨
동작
// AP 데이터 객체
static class AP {
int num;
int x;
int y;
int chargeRange;
int performance;
public AP(int num, int x, int y, int chargeRange, int performance) {
this.num = num;
this.x = x;
this.y = y;
this.chargeRange = chargeRange;
this.performance = performance;
}
public AP(int x, int y) {
this.x = x;
this.y = y;
}
} // End of AP class
AP의 정보를 담을 객체이다.
AP의 좌표값, x, y가 있고, 충전 범위 chargeRange 충전량 performance를 가지고 있다.
또한 AP를 구분하기 위해서 각 AP의 고윳값인 num을 만들어주었다.
해당 AP데이터를 저장할 배열 static AP[] apArr; 에 저장해준다.
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
userA[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
userB[i] = Integer.parseInt(st.nextToken());
}
각 유저의 방향 이동 정보를 배열에 담는다.
방향값을 index로 사용해서 현재 위치를 계산한다.
static int[] dirX = {0, -1, 0, 1, 0}; // 상 우 하 좌
static int[] dirY = {0, 0, 1, 0, -1};
for (int i = 0; i <= M; i++) {
List<AP> AtempList = new ArrayList<>();
List<AP> BtempList = new ArrayList<>();
for (AP ap : apArr) {
// Auser가 충전범위 안에 들어와있을 경우,
if (distCalc(userACoor.x, userACoor.y, ap.x, ap.y) <= ap.chargeRange) {
AtempList.add(ap);
}
// BUser가 충전범위에 들어온 경우,
if (distCalc(userBCoor.x, userBCoor.y, ap.x, ap.y) <= ap.chargeRange) {
BtempList.add(ap);
}
}
시간 순으로 진행을 하면서 값을 시간 별 최댓값을 찾고 총 합을 계산한다.
먼저 Auser, Buser 둘 중하나는 AP의 범위에 있어야 계산을 하므로, 시간 별 userA의 위치와 userB의 위치에서 AP의 좌표 거리를 계산해서 AP의 chargeRange 범위에 들어올 경우 각 유저의 tempList에 저장을 해서 경우의 수를 계산한다.
int AtempListSize = AtempList.size();
int BtempListSize = BtempList.size();
int maxValueByHour = 0;
if (AtempListSize > 0 && BtempListSize == 0) {
for (AP ap : AtempList) {
maxValueByHour = Math.max(maxValueByHour, ap.performance);
}
} else if (AtempListSize == 0 && BtempListSize > 0) {
for (AP ap : BtempList) {
maxValueByHour = Math.max(maxValueByHour, ap.performance);
}
} else if (AtempListSize > 0) {
// 서로 겹쳤을 경우, (가장 괜찮은 조합을 선택)
for (int j = 0; j < AtempListSize; j++) {
int aUserAP_Num = AtempList.get(j).num;
int aUserAP_Performance = AtempList.get(j).performance;
for (int k = 0; k < BtempListSize; k++) {
int bUserAP_Num = BtempList.get(k).num;
int bUserAP_Performance = BtempList.get(k).performance;
// 번호가 같을 경우 충전량이 절반으로 줄어듬
if (aUserAP_Num == bUserAP_Num) {
maxValueByHour = Math.max(maxValueByHour, (aUserAP_Performance / 2) * 2);
} else {
maxValueByHour = Math.max(maxValueByHour, aUserAP_Performance + bUserAP_Performance);
}
}
}
}
result += maxValueByHour;
다음은 각 user별 tempList의 size를 계산해서
조건별로 구분한다.
userA의 tempList만 size가 0보다 클 때, 이 경우는 AtempList에서 그냥 performance값을 가장 큰 값을 찾으면 됨
userB의 tempList만 size가 0보다 클 때도 같음
이제 userA와 userB 둘 다 size가 0보다 클 경우,
해당 경우는 user하나를 골라서 2차원 배열을 통해 각 AP를 전부 돌려보면 된다.
가령 userA의 apNum과 userB의 apNum이 같을 경우 그냥 userA의 apPerformance의 절반 값 * 2를 해주면 되고,
나머지는 서로 조합을 해서 최댓값이 나오는 경우를 모두 찾아보면 된다. 해당 경우가 완전탐색이 된다.
if (i == M) {
break;
}의 코드가 필요한 이유는 0초 부터 바로 충전이 시작될 수 있기 때문에 먼저 최댓값을 탐색하고, user의 방향을 옮기게된다.
여기서 시간이 M보다 커지면 안되기 때문에 방향 탐색을 더 이상 할 수 없도록 M이 되면 중지하도록 했다.
그 다음은 시간 별로 각 user의 좌표를 갱신하는 코드이다.
// 시간별 user의 좌표값 갱신
userACoor.x = dirX[userA[i]] + userACoor.x;
userACoor.y = dirY[userA[i]] + userACoor.y;
userBCoor.x = dirX[userB[i]] + userBCoor.x;
userBCoor.y = dirY[userB[i]] + userBCoor.y;
코드
Java
import java.util.*;
import java.io.*;
public class Solution {
static int M, A, result;
static int[] userA; // 시간 별 유저의 방향 값을 저장할 배열
static int[] userB;
static int[] dirX = {0, -1, 0, 1, 0}; // 상 우 하 좌
static int[] dirY = {0, 0, 1, 0, -1};
static AP userACoor; // 해당 유저의 현재 위치값
static AP userBCoor;
static AP[] apArr; // AP의 데이터가 저장된 배열
// AP 데이터 객체
static class AP {
int num;
int x;
int y;
int chargeRange;
int performance;
public AP(int num, int x, int y, int chargeRange, int performance) {
this.num = num;
this.x = x;
this.y = y;
this.chargeRange = chargeRange;
this.performance = performance;
}
public AP(int x, int y) {
this.x = x;
this.y = y;
}
} // End of AP class
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
sb.append('#').append(t).append(' ');
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken()); // 총 이동 시간
A = Integer.parseInt(st.nextToken()); // AP의 수
init(); // 변수 초기화 메소드
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
userA[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
userB[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < A; i++) {
st = new StringTokenizer(br.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());
apArr[i] = new AP(i, x, y, C, P);
}
// 시간 별 Max값을 구하기.
for (int i = 0; i <= M; i++) {
List<AP> AtempList = new ArrayList<>();
List<AP> BtempList = new ArrayList<>();
for (AP ap : apArr) {
// Auser가 충전범위 안에 들어와있을 경우,
if (distCalc(userACoor.x, userACoor.y, ap.x, ap.y) <= ap.chargeRange) {
AtempList.add(ap);
}
// BUser가 충전범위에 들어온 경우,
if (distCalc(userBCoor.x, userBCoor.y, ap.x, ap.y) <= ap.chargeRange) {
BtempList.add(ap);
}
}
int AtempListSize = AtempList.size();
int BtempListSize = BtempList.size();
int maxValueByHour = 0;
if (AtempListSize > 0 && BtempListSize == 0) {
for (AP ap : AtempList) {
maxValueByHour = Math.max(maxValueByHour, ap.performance);
}
} else if (AtempListSize == 0 && BtempListSize > 0) {
for (AP ap : BtempList) {
maxValueByHour = Math.max(maxValueByHour, ap.performance);
}
} else if (AtempListSize > 0) {
// 서로 겹쳤을 경우, (가장 괜찮은 조합을 선택)
for (int j = 0; j < AtempListSize; j++) {
int aUserAP_Num = AtempList.get(j).num;
int aUserAP_Performance = AtempList.get(j).performance;
for (int k = 0; k < BtempListSize; k++) {
int bUserAP_Num = BtempList.get(k).num;
int bUserAP_Performance = BtempList.get(k).performance;
// 번호가 같을 경우 충전량이 절반으로 줄어듬
if (aUserAP_Num == bUserAP_Num) {
maxValueByHour = Math.max(maxValueByHour, (aUserAP_Performance / 2) * 2);
} else {
maxValueByHour = Math.max(maxValueByHour, aUserAP_Performance + bUserAP_Performance);
}
}
}
}
result += maxValueByHour;
if (i == M) {
break;
}
// 시간별 user의 좌표값 갱신
userACoor.x = dirX[userA[i]] + userACoor.x;
userACoor.y = dirY[userA[i]] + userACoor.y;
userBCoor.x = dirX[userB[i]] + userBCoor.x;
userBCoor.y = dirY[userB[i]] + userBCoor.y;
}
sb.append(result).append('\n');
}
bw.write(sb.toString());
bw.close();
} // End of main
private static int distCalc(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
} // End of distCalc
private static void init() {
result = 0;
userA = new int[M];
userB = new int[M];
userACoor = new AP(1, 1); // userA의 시작점
userBCoor = new AP(10, 10); // userB의 시작점
apArr = new AP[A];
} // End of init
} // End of Main class
