[SWEA]#5644 [모의 SW 역량테스트] 무선 충전

SeungBird·2020년 9월 7일
0

⌨알고리즘(SWEA)

목록 보기
27/31

문제

#5644 [모의 SW 역량테스트] 무선 충전

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
테스트 케이스의 첫 번째 줄에는 총 이동 시간(M), BC의 개수(A)가 주어진다.
그 다음 2개의 줄에는 각각 사용자 A와 B의 이동 정보가 주어진다.
한 사용자의 이동 정보는 M개의 숫자로 구성되며, 각각의 숫자는 다음과 같이 매초마다 이동 방향을 의미한다.

숫자01234
이동 방향이동하지 않음상 (UP)우 (RIGHT)하 (DOWN)좌 (LEFT)

그 다음 줄에는 A개의 줄에 걸쳐 BC의 정보가 주어진다.
하나의 BC 정보는 좌표(X, Y), 충전 범위(C), 처리량(P)로 구성된다.

출력

출력은 "#t"를 찍고 한 칸 띄운 다음 정답을 출력한다. (t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)
정답은 모든 사용자의 충전량 합의 최대값을 출력한다.

예제 입력 1

5
20 3
2 2 3 2 2 2 2 3 3 4 4 3 2 2 3 3 3 2 2 3
4 4 1 4 4 1 4 4 1 1 1 4 1 4 3 3 3 3 3 3
4 4 1 100
7 10 3 40
6 3 2 70
…

예제 출력 1

#1 1200
#2 3290
#3 16620
#4 40650
#5 52710

풀이

이 문제는 문제에서 주어진 조건들을 정확히 구현하려고 코딩을 하면 문제없이 풀 수 있다. HashMap을 이용해서 BC의 정보를 저장하고 빠르게 검색할 수 있도록 구현했다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.HashMap;
import java.util.ArrayList;

class Solution
{
    static int[] dx = {0, -1, 0, 1, 0};
    static int[] dy = {0, 0, 1, 0, -1};
    static HashMap<Integer, Ap> map;

    public static void main(String args[]) throws Exception
    {
        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[] input = br.readLine().split(" ");
            int M = Integer.parseInt(input[0]);
            int N = Integer.parseInt(input[1]);
            int[] a = new int[M];
            int[] b = new int[M];
            map = new HashMap<>();
            int t = 0;
            Pair A = new Pair(1, 1);
            Pair B = new Pair(10, 10);
            int ans = 0;

            input = br.readLine().split(" ");
            for(int i=0; i<M; i++)
                a[i] = Integer.parseInt(input[i]);

            input = br.readLine().split(" ");
            for(int i=0; i<M; i++)
                b[i] = Integer.parseInt(input[i]);

            for(int i=0; i<N; i++) {
                input = br.readLine().split(" ");
                map.put(i, new Ap(Integer.parseInt(input[1]), Integer.parseInt(input[0]), Integer.parseInt(input[2]), Integer.parseInt(input[3])));
            }

            while(true) {
                ArrayList<Integer> listA = new ArrayList<>();
                ArrayList<Integer> listB = new ArrayList<>();
                int max = Integer.MIN_VALUE;

                for(int i=0; i<N; i++) {
                    Ap ap = map.get(i);
                    if(Math.abs(A.x-ap.x)+Math.abs(A.y-ap.y)<=ap.c)
                        listA.add(i);

                    if(Math.abs(B.x-ap.x)+Math.abs(B.y-ap.y)<=ap.c)
                        listB.add(i);
                }

                if(listA.size()==0 && listB.size()==0) {
                    max = 0;
                }

                else if(listA.size()==0 || listB.size()==0) {
                    if(listA.size()==0) {
                        for(int i=0; i<listB.size(); i++) {
                            int idx = listB.get(i);
                            Ap y = map.get(idx);
                            max = Math.max(max, y.p);
                        }
                    }

                    else {
                        for(int i=0; i<listA.size(); i++) {
                            int idx = listA.get(i);
                            Ap x = map.get(idx);
                            max = Math.max(max, x.p);
                        }
                    }
                }

                else {
                    for(int i=0; i<listA.size(); i++) {
                        int idx1 = listA.get(i);
                        Ap x = map.get(idx1);
                        for(int j=0; j<listB.size(); j++) {
                            int idx2 = listB.get(j);
                            Ap y = map.get(idx2);
                            int sum = 0;

                            if(idx1==idx2)
                                sum = x.p;

                            else
                                sum = x.p+y.p;

                            max = Math.max(max, sum);
                        }
                    }
                }
                ans += max;

                if(t>=M) break;
                int ax = A.x+dx[a[t]];
                int ay = A.y+dy[a[t]];
                int bx = B.x+dx[b[t]];
                int by = B.y+dy[b[t]];
                A = new Pair(ax, ay);
                B = new Pair(bx, by);
                t++;
            }
            System.out.println("#"+test_case+" "+ans);
        }
    }

    public static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static class Ap {
        int x;
        int y;
        int c;
        int p;

        public Ap(int x, int y, int c, int p) {
            this.x = x;
            this.y = y;
            this.c = c;
            this.p = p;
        }
    }
}
profile
👶🏻Jr. Programmer

0개의 댓글