SWEA[5644] - 무선 충전기

링크

SWEA[5644]

문제설명

• 시뮬레이션

문제풀이

• 시뮬레이션 + 완전탐색

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution5644 {
    public static int [][] Ch; 
    public static int[][] dir = {     //    숫자   이동 방향
            {0,0},                    //    0          이동하지 않음
            {-1,0},                   //    1          상 (UP)
            {0,1},                    //    2          우 (RIGHT)
            {1,0},                    //    3          하 (DOWN)
            {0,-1}                    //    4          좌 (LEFT)
    };

    public static int Search(ArrayList<Integer> al, ArrayList<Integer> bl) {
        int max=0;
        for (int i = 0; i < al.size(); i++) {
            for (int j = 0; j < bl.size(); j++) {
                if(al.get(i)==bl.get(j)) {
                    max = Math.max(max, Ch[al.get(i)][3]);    //같으면 둘이 나눠먹음
                }
                else {    //다르면 각각 더해줌
                    max = Math.max(max, Ch[al.get(i)][3]+Ch[bl.get(j)][3]);
                }
            }
        }
        return max;
    }

    public static int Search(ArrayList<Integer> al) {
        int max=0;
        for (int i = 0; i < al.size(); i++) {
            max = Math.max(max, Ch[al.get(i)][3]);
        }
        return max;
    }

    public static int len(int x1, int y1, int x2, int y2) {
        return Math.abs(x1-x2) + Math.abs(y1-y2);
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/5644.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        int T=Integer.parseInt(br.readLine().trim());

        for (int test_case = 1; test_case <= T; test_case++) {
            int ans=0;
//            입력
            StringTokenizer st = new StringTokenizer(br.readLine().trim()," ");
            int M = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            int[] A = new int [M];
            int ay=1;
            int ax=1;

            int[] B = new int [M];
            int by=10;
            int bx=10;

            st = new StringTokenizer(br.readLine().trim()," ");
            for (int i = 0; i < M; i++) {
                A[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine().trim()," ");
            for (int i = 0; i < M; i++) {
                B[i] = Integer.parseInt(st.nextToken());
            }

            Ch = new int [C][4];    //{X,Y,범위,성능}
            for (int i = 0; i < C; i++) {
                st = new StringTokenizer(br.readLine().trim()," ");
                for (int j = 0; j < 4; j++) {
                    Ch[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            ArrayList<Integer> al = new ArrayList<>();
            ArrayList<Integer> bl = new ArrayList<>();
            int debug=0;

//            초기 경우 check
            for (int j = 0; j < C; j++) {
                if(len(ax,ay,Ch[j][0],Ch[j][1])<=Ch[j][2]) {    //송신탑 범위안에 들어옴
                    al.add(j);
                }
                if(len(bx,by,Ch[j][0],Ch[j][1])<=Ch[j][2]) {    //송신탑 범위안에 들어옴
                    bl.add(j);
                }
            }
            if(al.isEmpty()&&bl.isEmpty()) {

            }
            else if(al.isEmpty()&&!bl.isEmpty()) {
                ans+=Search(bl);
            }
            else if(!al.isEmpty()&&bl.isEmpty()) {
                ans+=Search(al);
            }
            else {    //둘 다 비어있지 않은 경우
                ans+=Search(al, bl);
            }
            al.clear();
            bl.clear();

//            움직임 실행

            for (int i = 0; i < M; i++) {
                ay += dir[A[i]][0];
                ax += dir[A[i]][1];
                by += dir[B[i]][0];
                bx += dir[B[i]][1];
//            움직인 이후 송신탑과 거리안에 든것들 check    
                for (int j = 0; j < C; j++) {
                    if(len(ax,ay,Ch[j][0],Ch[j][1])<=Ch[j][2]) {    //송신탑 범위안에 들어옴
                        al.add(j);
                    }
                    if(len(bx,by,Ch[j][0],Ch[j][1])<=Ch[j][2]) {    //송신탑 범위안에 들어옴
                        bl.add(j);
                    }
                }
                if(al.isEmpty()&&bl.isEmpty()) {
                    int d=0;
                }
                else if(al.isEmpty()&&!bl.isEmpty()) {
                    ans+=Search(bl);
                }
                else if(!al.isEmpty()&&bl.isEmpty()) {
                    ans+=Search(al);
                }
                else {    //완전탐색
                    ans+=Search(al, bl);
                }
                al.clear();
                bl.clear();
            }

            System.out.println("#"+test_case+" "+ans);
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}

아쉬운점

• 겹칠 경우 상위 2개 정렬 후 비교하려고 했으나, 여러경우의 수가 생김
  • 그냥 모든 경우의 수를 고려했어야 했다.
• 시작위치에서도 계산하는거 고려안했었음
• 정렬 후 상위 2개값만 비교해도 문제가 되지 않음
  • A: 1, 1000
  • B: 2, 1000
  • 어떤짓을해도 나눠먹는건 손해임

잘한점

• 메서드 적절하게 만들어서 씀
• Search 메서드 오버로딩함