알고리즘/알고리즘문풀
SW Expert Academy - 무선 충전 (JAVA)
developer-ellen
2022. 2. 17. 00:18
❓ 문제 - SW Expert Academy 무선 충전 JAVA 풀이법
출처
(https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo)
📝 문제해결법
1. 이 문제는 시뮬레이션 + 중복조합으로 풀었다.
- 사용자(A, B)의 입장으로 시뮬레이션을 구현하였다.
- c_list에 무선충전기의 대한 정보를 Charger라는 클래스를 통해 객체로 만든 후 ArrayList에 add했다.
- A, B가 움직이는 시간 0 ~ M 에서 각 초에 대한 움직임으로 얼만큼 충전하는지 구현하였다.
- 우선 A, B가 처음에 있는 위치 (1, 1) , (10, 10)에서도 무선충전기의 영향 안에 있다면 충전 가능하다.
- A, B와 무선 충전기들 사이의 거리가 영향 아래 들어가 있으면 무선 충전기 범위 내에 있다는 것을 use 이차원 배열을 통해 표시 하였다.
- <<가장 힘든 부분>> A, B가 어떤 충전기를 사용해서 충전할지 결정하는 부분을 중복 조합스럽게 구현하였다.
- A,B가 선택할 수 있는 모든 충전기를 고려하여 최대 충전량을 구하는 것이 특징이다.
- A,B가 만약 1개 이상의 충전기 범위 내에 있고, A,B가 만약 같은 충전기를 사용할 때는 temp_sum은 그 공유하는 충전기의 양이다.(각 자 충전량 나누기 2하고 다시 2곱하기 때문)
- A,B가 만약 1개 이상의 충전기 범위 내에 있지만 둘은 다른 충전기 범위에 있을 때는 temp_sum은 각각 범위 내에 속한 충전기의 충전량을 더한 값이다.
- A만 1개 이상의 충전기 범위 내에 속한다면 temp_sum은 해당 충전기의 충전량 값이다.
- B만 1개 이상의 충전기 범위 내에 속한다면 temp_sum은 해당 충전기의 충전량 값이다.
- A,B가 선택할 수 있는 모든 충전기를 중복조합으로 구하고 그 때마다 위와 같이 구한 temp_sum을 sum에 최대값으로 갱신한다.
- 마지막에 sum값을 ans에 더하고 모든 초에 움직이면서 구한 ans값을 출력한다.
2. 느낀점
- 자바로 시뮬레이션 처음 풀어보는데... ArrayList로 관리하는 것들이 익숙하지 않아 처음에 애먹었다..
- 그 후 에 A,B가 어떤 충전기를 선택해서 충전해야 최대 충전량 합인지 찾는 것을 구현하는 것도 어려웠음...
- 위에 해결하여 구현한 후 SWEA에 돌려보니 계속 39/50 개만 맞아서... 왜 그럴까 고민하다가 문제 자세히 보니 처음에 움직이지 않은 상태에도 무선충전기 범위 내에 있으면 충전한다라는 것이 있었다...!
- 이 문제를 풀며 느낀 것은.. 우선 자바를 통해 시뮬레이션을 많이 풀어보자 ! 그리고 경우의 수가 생각보다 적다면 하나하나 다 조건을 걸어서 탐색해보는 방법도 생각하기! 그리고... 문제를 잘 읽자 ^_^
💻 소스코드
// SWEA - 무선충전(5466번)
// 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Solution_5644 {
public static class Charger{
int x;
int y;
int c;
int p;
public Charger(int x, int y, int c, int p){
this.x = x;
this.y = y;
this.c = c;
this.p = p;
}
}
public static int[] dx = {0, -1, 0, 1, 0};
public static int[] dy = {0, 0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int test_case=1;test_case <= T;test_case++){
String[] data = br.readLine().split(" ");
int m = Integer.parseInt(data[0]);
int a = Integer.parseInt(data[1]);
int[] move_a = new int[m];
int[] move_b = new int[m];
String[] data2 = br.readLine().split(" ");
String[] data3 = br.readLine().split(" ");
for(int i=0;i<m;i++){
move_a[i] = Integer.parseInt(data2[i]);
move_b[i] = Integer.parseInt(data3[i]);
}
ArrayList<Charger> c_list = new ArrayList<>();
int a_x = 1;
int a_y = 1;
int b_x = 10;
int b_y = 10;
int ans = 0;
for(int i=0;i<a;i++){
String[] input = br.readLine().split(" ");
int y = Integer.parseInt(input[0]);
int x = Integer.parseInt(input[1]);
int c = Integer.parseInt(input[2]);
int p = Integer.parseInt(input[3]);
c_list.add(new Charger(x, y, c, p));
}
// 움직이기 ! i가 -1일땐 처음 이동하지 않은 상태에서 충전기의 영향 받을 때 살핌
for(int i=-1;i<m;i++){
if(i != -1) {
a_x += dx[move_a[i]];
a_y += dy[move_a[i]];
b_x += dx[move_b[i]];
b_y += dy[move_b[i]];
}
int[][] use = new int[2][a];
for(int j=0;j<a;j++){
Charger cr = c_list.get(j);
if((Math.abs(cr.x-a_x)+ Math.abs(cr.y-a_y)) <= cr.c){
use[0][j] += 1;
}
if((Math.abs(cr.x-b_x)+ Math.abs(cr.y-b_y)) <= cr.c){
use[1][j] += 1;
}
}
// A, B의 충전합을 최대로 할 충전기의 중복 조합 탐색...
int sum = 0;
for(int p=0;p<a;p++){
for(int q=0;q<a;q++){
int temp_sum = 0;
if(use[0][p] == 1){
if(use[1][q] == 1){
if(p == q){
temp_sum = c_list.get(p).p;
} else {
temp_sum = (c_list.get(p).p + c_list.get(q).p);
}
} else {
temp_sum = c_list.get(p).p;
}
} else {
if(use[1][q] == 1){
temp_sum = c_list.get(q).p;
}
}
sum = Math.max(temp_sum, sum);
}
}
ans += sum;
}
System.out.println("#"+test_case+" "+ans);
}
}
}