1
1
// Authored by : qhsl1213
2
2
// Co-authored by : BaaaaaaaaaaarkingDog
3
- // http://boj.kr/2daca686c11041b190d57441bd7f5467
3
+ // http://boj.kr/b16516f45f5b4e2db278b6aa3f224e42
4
4
#include < bits/stdc++.h>
5
5
using namespace std ;
6
6
typedef long long ll;
@@ -20,8 +20,8 @@ int main(void) {
20
20
for (int j = i+1 ; j < N; j++){
21
21
int idx = lower_bound (sol, sol+N, -sol[i] - sol[j]) - sol;
22
22
23
- // idx-2, idx-1, idx, idx+1, idx+2 위치에 있는 용액이 최적일 수 있다.
24
- for (int k = -2 ; k <= 2 ; k++){
23
+ // idx-3, idx- 2, idx-1, idx, idx+1, idx+2 위치에 있는 용액이 최적일 수 있다.
24
+ for (int k = -3 ; k <= 2 ; k++){
25
25
if (idx+k == i || idx+k == j) continue ;
26
26
if (idx+k < 0 || idx+k >= N) continue ;
27
27
if (abs (ans[0 ] + ans[1 ] + ans[2 ]) > abs (sol[i] + sol[j] + sol[idx+k]))
@@ -35,15 +35,23 @@ int main(void) {
35
35
36
36
/*
37
37
세 개의 "서로 다른 용액"을 혼합해야 한다는 점에 주의해야 한다.
38
- "idx-2, idx-1, idx, idx+1, idx+2 위치에 있는 용액이 최적일 수 있다."는 주석에 설명을 추가하면,
38
+ "idx-3, idx-2, idx-1, idx, idx+1, idx+2 위치에 있는 용액이 최적일 수 있다."는 주석에 설명을 추가하면,
39
+ lower_bound의 특성상 sol[idx]는 -sol[i] - sol[j] 이상인 최초의 인덱스이고, 다르게 설명하면
40
+ sol[i] + sol[j] + sol[idx]는 0 혹은 양수 중에서 절댓값이 제일 작은 인덱스이다. 또한
41
+ sol[i] + sol[j] + sol[idx-1]은 자연스럽게 음수 중에서 절댓값이 제일 작은 인덱스이다.
42
+ 그렇기 때문에 용액의 중복이 허용되면 sol[idx]와 sol[idx-1]만을 고려하면 되나 "서로 다른 용액"을 혼합해야 하기 때문에
43
+ 양수 쪽에서는 만약 i = idx, j = idx+1일 때 idx+2까지 고려를 해야 하고 음수 쪽에서는 i = idx-1, j = idx-2일 때
44
+ idx-3까지 고려를 해야 한다.
39
45
40
- -10 -7 -5 -2 1 1000 1001 1002
46
+ 실제로
41
47
42
- 과 같은 예제를 생각해보자. 여기서 i = 3, j = 4인 경우 sol[3] = -2, sol[4] = 1에 대해서
43
- abs(sol[3] + sol[4] + sol[k])가 최소인 k를 찾고자 한다. (단 k != i, k != j. 이 경우 k = 2이다.)
48
+ -3 -2 -1 100
44
49
45
- 21번째줄의 idx는 계산을 해보면 4가 되는데, 서로 다른 용액을 혼합해야 한다는 조건으로 인해
46
- 최대 idx-2까지 탐색을 해야 주어진 i, j에 대한 올바른 k를 구할 수 있다.
50
+ 과 같은 예제를 생각해보자. 여기서 i = 1, j = 2인 경우 sol[1] = -2, sol[2] = -1에 대해서
51
+ abs(sol[3] + sol[4] + sol[k])가 최소인 k를 찾고자 한다. (단 k != i, k != j. 이 경우 k = 0이다.)
52
+
53
+ 21번째줄의 idx는 계산을 해보면 3이 되는데, 서로 다른 용액을 혼합해야 한다는 조건으로 인해
54
+ 최대 idx-3까지 탐색을 해야 주어진 i, j에 대한 올바른 k를 구할 수 있다.
47
55
48
56
idx+2까지 탐색을 해야하는 예제도 아래와 같이 쉽게 구성할 수 있다.(i = 1, j = 2일 때)
49
57
@@ -55,5 +63,5 @@ idx+2까지 탐색을 해야하는 예제도 아래와 같이 쉽게 구성할
55
63
i = b, j = c일 때 "idx-1, idx, idx+1" 위치만 확인할 경우 k를 잘못 구할 수 있지만,
56
64
적어도 i = a, j = c일 때에는 k = b를 잘 찾을 수 있기 때문이다.
57
65
58
- 그러나 이 내용을 관찰하지 못할 수 있으니 그냥 idx-2부터 idx+2까지 확인하도록 코드를 구성했다.
66
+ 그러나 이 내용을 관찰하지 못할 수 있으니 그냥 idx-3부터 idx+2까지 확인하도록 코드를 구성했다.
59
67
*/
0 commit comments