반응형

문제풀이

상당히 어렵게 푼 문제이다. 단순히 구현하는 문제(시뮬레이션)인데 공유하는 BC가 있을경우 선택을 잘 해야한다.

유저 a와 b의 경로를 2차원 배열에 저장하고 이동이 끝나면 시작위치의 좌표를 재조정한다.

이때 1) 유저 a만 충전하는 경우 2) 유저 b만 충전하는 경우 3) 유저 a,b 모두 충전하는 경우

총 3가지로 나누어 처리하였다.


소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct BC{
    int x, y, c, p;
}BC;
vector<BC> bc;
int ax, ay, bx, by;
int m, a, c, p;
int chargeA, chargeB;
// 정지, 상, 우, 하, 좌
int dx[]={0010-1};
int dy[]={0-1010};
int userPath[2][101];
 
int solve() {
    ax=ay=1;
    bx=by=10;
    chargeA=chargeB=0;
 
    for (int k=0; k<=m; k++) {
        vector<int> a,b;
        for (int i=0; i<bc.size(); i++) {
            if (abs(ax - bc[i].x) + abs(ay - bc[i].y) <= bc[i].c) 
                a.push_back(i);
            if (abs(bx - bc[i].x) + abs(by - bc[i].y) <= bc[i].c) 
                b.push_back(i);
        }
 
        int pA=0, pB=0, tmpSum=0;
        if (!a.empty() && b.empty()) {
            for (int i=0; i<a.size(); i++) {
                int tmpA = bc[a[i]].p;
                if (tmpSum < tmpA) {
                    tmpSum = tmpA;
                    pA = tmpA;
                }
            }
        }
        else if (a.empty() && !b.empty()) {
            for (int i=0; i<b.size(); i++) {
                int tmpB = bc[b[i]].p;
                if (tmpSum < tmpB) {
                    tmpSum = tmpB;
                    pB = tmpB;
                }
            }
        }
        else {
            for (int i=0; i<a.size(); i++) {
                for (int j=0; j<b.size(); j++) {
                    int tmpA = bc[a[i]].p;
                    int tmpB = bc[b[j]].p;
                    if (a[i] == b[j]) {
                        tmpA/=2;
                        tmpB/=2;
                    }
                    if (tmpSum < tmpA+tmpB) {
                        tmpSum = tmpA+tmpB;
                        pA = tmpA;
                        pB = tmpB;
                    }
                }
            }
        }
 
        ax += dx[userPath[0][k]];
        ay += dy[userPath[0][k]];
        bx += dx[userPath[1][k]];
        by += dy[userPath[1][k]];
        chargeA += pA;
        chargeB += pB;
    }
    return chargeA + chargeB;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc;
    cin>>tc;
    for (int t=1; t<=tc; t++) {
        cin>>m>>a;
        memset(userPath[0], 0sizeof(userPath[0]));
        memset(userPath[1], 0sizeof(userPath[1]));
        bc.clear();
 
        for (int i=0; i<m; i++cin>>userPath[0][i];
        for (int i=0; i<m; i++cin>>userPath[1][i];
 
        int y, x;
        for (int i=0; i<a; i++) {
            cin>>x>>y>>c>>p;
            bc.push_back(BC{x, y, c, p});
        }
 
        cout<<"#"<<t<<" "<<solve()<<"\n";
    }
    return 0;
}
cs


반응형

'Algorithm' 카테고리의 다른 글

[BOJ 13460] 구슬 탈출2  (0) 2019.10.09
[SWEA 1953] 탈주범 검거  (0) 2019.08.23
[SWEA 1949] 등산로 조성  (0) 2019.08.19
[SWEA 1208] Flatten  (0) 2019.07.29
[SWEA 1219] 길찾기  (0) 2019.07.24

+ Recent posts