[ SWEA 5644 ] 무선 충전 (C++)

SWExpertAcademy의 무선충전(5644) 문제이다.

[ 문제풀이 ]

1) 문제가 복잡해 보이지만 단순하게 생각하면 나름 단순한 문제인 것 같다. 천천히 알아가보도록 하자.

   먼저 입력에 관한 부분이다. 문제의 예시들과 그림들을 잘 보면 입력으로 주어지는 좌표들은 실제 x, y축이 있는 좌표에서의

   (x, y)값이 주어진다.

   ( 이 부분에 관한 설명은 원래 x축 y축으로 받는 분들은 상관이 없습니다 ! 본인은 행렬처럼 x를 세로축 y를 가로축으로 사용해서

     입력 좌표를 조금 바꿔줘야 해서 설명하는 부분입니다. )

   즉, 우리가 사용하는 2차원 맵에 표시를 해주기 위해서는 y와 x축을 바꿔줘야 한다. 또한, 본인은 맵의 범위를 (1, 1)  ~ (10, 10)이

   아닌 (0, 0) ~ (9, 9)로 잡아주었기 때문에 입력받는 좌표의 x와 y값을 바꿔줌과 동시에 -1도 해 주었다.

2) 이제는 2명의 사람을 각각 움직여 주면서 충전할 수 있는 칸이라면 충전을 시키기만 하면 되는데 몇 가지 문제가 있다.

   바로 BC가 겹치는 영역들과 사람끼리 겹치는 경우가 있기 때문이다.

   문제에서 말했듯이, 예를들어서 충전량이 100인 BC에 사람이 2명이 동시에 사용하게 되면 50 씩 나눠 쓰게 된다.

   생각해보면 고려해야 될 것이 엄청 많아 보인다.

   1. 현재 영역에 BC의 갯수 ?

   2. 현재 영역에 사람의 갯수 ?

   3. 현재 영역에 BC도 여러개 겹치고 사람도 겹치면 ?

   뭐 이런경우들을 생각할 수도 있는데 복잡하게 생각할 필요 없다.

   문제의 핵심은 두 사람이 사용한 최대 충전량을 묻는 것이다. 두 사람 중 더 많이 사용한 사람의 충전량을 묻는것도 아니고

   "두 사람이 사용한 충전량의 총합" 에서 최대가 되는 값을 구해야 하는 것이다. 

   지금부터 사람을 A와 B로 표현하겠다. 본인은 크게 3가지 조건으로 나누어 주었다.

   1. A가 사용할 수 있는 BC가 없는 경우

   2. B가 사용할 수 있는 BC가 없는 경우

   3. A와 B 둘다 사용할 수 있는 BC가 1개 이상인 경우

   위의 3가지 조건을 한번 해결해보자.

   1번 조건. A가 사용할 수 있는 BC가 없는경우이다.

   A가 사용할 수 있는 BC가 없는 경우에 A의 충전량은 당연히 0이된다. 그렇다면 B의 충전량은 얼마가 될까 ?

   B 또한 사용할 수 있는 BC가 없을 경우에는 0.

   B가 1개의 BC를 사용할 수 있을 경우에는 해당 BC의 P 값.

   B가 2개 이상의 BC를 사용할 수 있을 경우에는 BC의 P값들 중 최댓값.

   반대인 2번 조건도 똑같다. 단지 A와 B의 위치만 바뀌었을 뿐.

   문제는 3번 조건이다. 둘 다 사용할 수 있는 BC가 1개 이상인 경우이다. 사람끼리 겹치는지 안겹치는지는 아직까지는 모른다.

   본인은, 현재 A와 B가 있는 곳에서 사용할 수 있는 BC의 번호를 Vector에 임시적으로 담아두었다.

   예를 들어서 A가 1번과 2번 BC를 사용할 수 있고, B가 1번과 3번 BC를 사용할 수 있다면

   A의 Vector에는 {1, 2} 가, B의 Vector에는 {1, 3} 이 들어가 있을 것이다.

   이제는 이 중에서 최댓값을 골라야 한다. 위의 예를 빗대서 { A가 사용하는 BC, B가 사용하는 BC }의 쌍으로

   표현해보면 { 1, 1 } , { 1, 3 } , { 2, 1 }, { 2, 3 } 이렇게 총 4가지 경우가 나올 것이다.

   저렇게 딱 4가지 경우에 대해서 같은 BC일 경우에는 2로 나눠준 후에 막 ~~ 그렇게 계산을 해서 최댓값을 찾으면 된다 ?

   위의 경우는 BC가 3개인 경우일 뿐이다. 정말 최악의 케이스로 BC의 최대갯수인 BC 8개에 사람이 겹친다고 생각하면 너무나도

   많은 경우의 수를 계산해 주어야 한다.

   복잡한 계산 같지만 사실 2중 for문이면 해결이 가능하다.

   왜냐하면 사람이 "2"명 이기 때문이다. 사람의 수가 랜덤적인것이 아닌 딱 2명만 존재하기 때문이다.

   본인이 위에서 말했듯이, 본인은 현재 위치에서 A와 B가 사용할 수 있는 BC의 번호를 Vector에 저장해 두었다고 했다.

   말로 설명하기 너무 어려운 부분이 있어서 아래의 코드부터 보고 설명을 계속 보도록 하자.

for (int i = 0; i < A_Use.size(); i++)        // A_Use는 A가 사용할 수 있는 BC를 저장한 Vector
{
    int A_BC = A_Use[i];
    for (int j = 0; j < B_Use.size(); j++)   // B_Use는 B가 사용할 수 있는 BC를 저장한 Vector
    {
        int B_BC = B_Use[j];

        if (A_BC == B_BC) Max_Energy = Bigger(Max_Energy, B[A_BC].P);
        else Max_Energy = Bigger(Max_Energy, B[A_BC].P + B[B_BC].P);
    }
}
return Max_Energy;

    위의 코드처럼 2중 for문으로 나타낼 수가 있다.

    BC가 겹치는 경우에는 그냥 그 BC의 P값을 계산해주었다. 왜 이렇게 계산이 가능할까??

    우리가 구해야 할 것은 "두 사람이 사용한 총량" 이다. 즉, P가 100인 BC를 2사람이 나눠서 50 50 씩 쓴다고 하더라도

    결국 두 사람이 사용한 총량은 BC의 P값인 100이 된다. 따라서 BC의 P값을 나눠주는 계산을 할 필요가 없다.

    BC가 겹치지 않는 경우에는 각각의 BC값들을 더해서 계산을 해주면 된다.

   

    본인도 사실 처음에 이걸 조합으로 짜야하나 순열로 짜야하나 고민을 했었는데 생각해보니 사람이 2명이라는 것 때문에

    단순 2중 for문으로도 해결이 가능했다.

    잊지말자. 우리가 구해야할 것은 "두 사람이 사용한 최대 충전량" 이라는 것을 !

  

[ 소스코드 ]

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167