SW Expert Academy - 무선 충전 (JAVA)

❓ 문제 - 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);

        }
    }
}