8000 Update 2473.cpp · dkim-coder/basic-algo-lecture@7680190 · GitHub
[go: up one dir, main page]

Skip to content

Commit 7680190

Browse files
Update 2473.cpp
1 parent 5368bfd commit 7680190

File tree

1 file changed

+18
-10
lines changed

1 file changed

+18
-10
lines changed

0x13/solutions/2473.cpp

Lines changed: 18 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
// Authored by : qhsl1213
22
// Co-authored by : BaaaaaaaaaaarkingDog
3-
// http://boj.kr/2daca686c11041b190d57441bd7f5467
3+
// http://boj.kr/b16516f45f5b4e2db278b6aa3f224e42
44
#include <bits/stdc++.h>
55
using namespace std;
66
typedef long long ll;
@@ -20,8 +20,8 @@ int main(void) {
2020
for(int j = i+1; j < N; j++){
2121
int idx = lower_bound(sol, sol+N, -sol[i] - sol[j]) - sol;
2222

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++){
2525
if(idx+k == i || idx+k == j) continue;
2626
if(idx+k < 0 || idx+k >= N) continue;
2727
if(abs(ans[0] + ans[1] + ans[2]) > abs(sol[i] + sol[j] + sol[idx+k]))
@@ -35,15 +35,23 @@ int main(void) {
3535

3636
/*
3737
세 개의 "서로 다른 용액"을 혼합해야 한다는 점에 주의해야 한다.
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까지 고려를 해야 한다.
3945
40-
-10 -7 -5 -2 1 1000 1001 1002
46+
실제로
4147
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
4449
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를 구할 수 있다.
4755
4856
idx+2까지 탐색을 해야하는 예제도 아래와 같이 쉽게 구성할 수 있다.(i = 1, j = 2일 때)
4957
@@ -55,5 +63,5 @@ idx+2까지 탐색을 해야하는 예제도 아래와 같이 쉽게 구성할
5563
i = b, j = c일 때 "idx-1, idx, idx+1" 위치만 확인할 경우 k를 잘못 구할 수 있지만,
5664
적어도 i = a, j = c일 때에는 k = b를 잘 찾을 수 있기 때문이다.
5765
58-
그러나 이 내용을 관찰하지 못할 수 있으니 그냥 idx-2부터 idx+2까지 확인하도록 코드를 구성했다.
66+
그러나 이 내용을 관찰하지 못할 수 있으니 그냥 idx-3부터 idx+2까지 확인하도록 코드를 구성했다.
5967
*/

0 commit comments

Comments
 (0)
0