SWEA 5644번: 무선 충전

문제

문제 바로가기> SWEA 5644번: 무선 충전

SW Expert Academy

 

풀이

input에서 주어진 경로를 따라 이동하면서, 다음과 같은 두 가지 경우로 나누어 문제를 해결해주면 된다. 

 

   1. 두 사용자가 동일한 위치에 있는 경우

      → 또 다시 3가지 경우로 나뉜다

          1) 주변에 충전 가능한 bc가 없는 경우 →  continue

          2) 1가지 bc를 나눠 사용해야 하는 경우

             → 1개의 bc를 각각 나눠 사용한다. 어짜피 ans에 나눠서 더하나, 그 값을 더하나 같다.

          3) 2가지 이상의 bc가 있는 경우 → 제일 큰 파워를 가진 두 bc를 이용한다.

                                                                (나는 prioirty queue를 이용해주었다)

 

    2. 두 사용자의 위치가 다른 경우

      → 이 경우에는 최대 파워를 가지는 bc 조합을 찾아주어야 한다.

           물론 사용자 a 혹은 b 만 접근 가능한 bc가 있을 수 있고,

           둘다 접근 가능한 bc가 있을 수 있고,

           둘다 접근 가능한 bc가 없을 수 있지만,

           아래 코드가 이 모든 경우를 포함한다. 

           이 부분은 코드를 보면 바로 이해할 수 있을 것 같으니! 코드를 보자.

💡 첫번 째 for문 : a만 접근 가능한 bc
💡 두번 째 for문 : b만 접근 가능한 bc
💡 세번 째 for문 : a, b 둘다 접근 가능한 bc → a와 b가 같은 bc를 사용해서는 안됨

추가로, get_possible_charge() 함수는 사용할 수 있는 bc의 index들의 집합을 리턴해주는 함수이다.

 

C++

#include<iostream>
#include<queue>
#define TIME 101
using namespace std;

struct BC{int y, x, c, p;};
vector<BC> bc;

int M, A;
int pathA[TIME], pathB[TIME];
int dy[] = { 0, -1, 0, 1, 0 }; // 이동x 상 우 하 좌
int dx[] = { 0, 0, 1, 0, -1 };


void input() {
    cin >> M >> A; // 총 이동 시간, BC의 개수
    for (int i = 0; i < M; i++) cin >> pathA[i]; // 사용자 A의 이동 정보
    for (int i = 0; i < M; i++) cin >> pathB[i]; // 사용자 B의 이동 정보

    int y, x, c, p;
    for (int i = 0; i < A; i++) { // BC의 정보
        cin >> x >> y >> c >> p; // 좌표(X, Y), 충전 범위(C), 처리량(P)
        bc.push_back({y, x, c, p});
    }
}

vector<int> get_possible_charge(int y, int x){
    vector<int> res;
    for(int i=0; i<A; i++){
        if(abs(y-bc[i].y)+abs(x-bc[i].x) <= bc[i].c) res.push_back(i);
    } return res;
}

int solution() { //  모든 사용자의 충전량 합의 최대값

    int ans = 0;
    int ay, ax, by, bx;
    ay = ax = 1; by = bx = 10;

    int da, db; // a, b의 이동방향 
    for(int i=-1; i<M; i++){ // 사용자는 초기 위치(0초)부터 충전할 수 있음 
        
        if(0<=i){ 
            da = pathA[i]; ay+=dy[da]; ax+=dx[da]; // a 이동
            db = pathB[i]; by+=dy[db]; bx+=dx[db]; // b 이동
        }

        if(ay==by && ax==bx){ // 두 사용자의 위치가 같은 경우 
            vector<int> pab = get_possible_charge(ay, ax);
            if(pab.size() == 0) continue; // 0개
            else if(pab.size()==1) ans+=bc[pab[0]].p; // 1개
            else{ // 2개 이상
                priority_queue<int> pq;
                for(int a=0; a<pab.size(); a++) pq.push(bc[pab[a]].p);
                ans+=pq.top(); pq.pop(); // first
                ans+=pq.top(); // second
            }
        }
        else{ // 위치가 다른 경우

            vector<int> pa = get_possible_charge(ay, ax); // a 충전
            vector<int> pb = get_possible_charge(by, bx); // b 충전

            // 최대가 되는 조합을 찾음
            priority_queue<int> pq;
            for(int a=0; a<pa.size(); a++) pq.push(bc[pa[a]].p);
            for(int b=0; b<pb.size(); b++) pq.push(bc[pb[b]].p);
            for(int a=0; a<pa.size(); a++) {
                for(int b=0; b<pb.size(); b++){
                    if(pa[a]!=pb[b]) pq.push(bc[pa[a]].p+bc[pb[b]].p);
                }
            }
            if(!pq.empty()) ans+=pq.top();
        }
    } 
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T; // 테스트 케이스의 개수 T
    for (int t = 1; t <= T; t++) {
        bc.clear(); // init
        input();
        cout << "#" << t << " " << solution() << "\n";
    }
}

 

Java

import java.io.*;
import java.util.*;

    public class Solution {

    static BufferedReader br = null;
    static StringBuilder sb = new StringBuilder();

    static final int dy[] = { 0, -1, 0, 1, 0 }; // 이동x 상 우 하 좌
    static final int dx[] = { 0, 0, 1, 0, -1 };

    static int M, A;
    static int[][] bc;
    static int[] pathA, pathB; 

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++){
            input();
            sb.append("#"+t+" "+solution()+"\n");
        }
        System.out.println(sb.toString());
    }
	
    static void input() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken()); // 총 이동 시간
        A = Integer.parseInt(st.nextToken()); // BC의 개수
        pathA = new int[M]; 
        pathB = new int[M];
        bc = new int[A][4];

        st = new StringTokenizer(br.readLine()); // 사용자 A의 이동 정보
        for (int i = 0; i < M; i++) pathA[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()); // 사용자 B의 이동 정보
        for (int i = 0; i < M; i++) pathB[i] = Integer.parseInt(st.nextToken());

        for (int i = 0; i < A; i++) { // BC의 정보
            st = new StringTokenizer(br.readLine()); // 좌표(X, Y), 충전 범위(C), 처리량(P)
            bc[i][1] = Integer.parseInt(st.nextToken()); // y
            bc[i][0] = Integer.parseInt(st.nextToken()); // x
            bc[i][2] = Integer.parseInt(st.nextToken()); // c
            bc[i][3] = Integer.parseInt(st.nextToken()); // p
        }
    }
	
    static int[] get_possible_charge(int y, int x){
        int[] res = new int[A];
        int idx = 0;
        for(int i=0; i<A; i++){
            if(Math.abs(y-bc[i][0])+Math.abs(x-bc[i][1]) <= bc[i][2]) res[idx++] = i;
        } return Arrays.copyOf(res, idx);
    }

    static int solution(){ 
        int ans = 0;
        int ay=1, ax=1, by=10, bx=10;

        for(int i=-1; i<M; i++){ // 사용자는 초기 위치(0초)부터 충전할 수 있음 

            if(0<=i){ 
                int da = pathA[i]; ay+=dy[da]; ax+=dx[da]; // a 이동
                int db = pathB[i]; by+=dy[db]; bx+=dx[db]; // b 이동
            }

            if(ay==by && ax==bx){ // 두 사용자의 위치가 같은 경우 
                int[] pab = get_possible_charge(ay, ax);
                if(pab.length == 0) continue; // 0개
                else if(pab.length==1) ans+=bc[pab[0]][3]; // 1개
                else{ // 2개 이상
                    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
                    for(int a=0; a<pab.length; a++) pq.offer(bc[pab[a]][3]);
                    ans+=pq.peek(); pq.poll(); // first
                    ans+=pq.peek(); // second
                }
            }
            else{ // 위치가 다른 경우

                int[] pa = get_possible_charge(ay, ax); // a 충전
                int[] pb = get_possible_charge(by, bx); // b 충전

                // 최대가 되는 조합을 찾음
                PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
                for(int a=0; a<pa.length; a++) pq.offer(bc[pa[a]][3]);
                for(int b=0; b<pb.length; b++) pq.offer(bc[pb[b]][3]);
                for(int a=0; a<pa.length; a++) {
                    for(int b=0; b<pb.length; b++){
                        if(pa[a]!=pb[b]) pq.offer(bc[pa[a]][3]+bc[pb[b]][3]);
                    }
                }
                if(!pq.isEmpty()) ans+=pq.poll();
            }
        } 
        return ans;
    }
}