2470 두 용액

이걸 어떻게 투포인터로 하지 

막 고민하다가 고민하다가.. (위 사진은 고민의 흔적들 tmi)

 

 

 

결국 이렇게 하면 될 것 같았다. 

 

먼저 정렬을 하고 l = 0, r = 1로 둔다. 

그 다음 r을 앞으로 한 칸씩 옮기면서 sum값이 더 나아지는지 확인한다. 

만약 sum값이 더 나아지지 않으면 r을 옮기는 걸 중지하고 l을 앞으로 옮기기 시작한다. 

l을 옮기다 sum값이 다시 안 좋아지면 그때는 중지하고 출력..

 

그런데 틀렸다. 음.. 엄.. 깨끗하고 맑은 정신으로 내일 다시 풀어봐야겠다. 

지금 생각해보는데 이렇게 하면 허점이 있을 것 같음 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

i64 absF(i64 n){
    if(n < 0)
        n *= -1;
    return n;
}

bool isBetter(i64 sum, int now, int forword){
    i64 nex_sum = sum -now + forword;
    if(absF(nex_sum) < absF(sum))
        return true;
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    vector <int> v(n);
    
    for(int i = 0; i < n; i++){
        scanf("%d", &v[i]);
    }
    
    sort(v.begin(), v.end());
    
    int l=0, r=1;
    i64 sum = v[l] + v[r];
    bool stopR = false;
    
    while(true){
        if(!stopR){
            if(isBetter(sum, v[r], v[r+1])){
                sum = sum - v[r] + v[r+1];
                r++;
            }
            else{
                stopR = true;
            }
        }
        else {
            if(isBetter(sum, v[l], v[l+1])){
                sum = sum - v[l] + v[l+1];
                l++;
            }
            else{
                break;
            }
        }
    }
    
    printf("%d %d", v[l], v[r]);
    
    return 0;
}

 

 

음 다시 보니 내 알고리즘대로라면 저 녹색을 값으로 잡을듯

음 엄 음

 

 

---

다시 생각해서 이렇게 풀었다.

 

먼저 합을 구한다

l을 기준으로 잡는다

합보다 작은 r값을 찾기 위해 r을 한칸씩 당긴다

기존의 합보다 작아지면 합을 바꾸고 아니면 안 바꾸도록 짰다. 

 

종료조건 : l+1 == r일때

 

나름의 검증 과정도 지났는데 막상 코드로 짜보니 몇개는 제대로 동작을 안 한다ㅋㅋ

잠이 오니 다시 내일로!

조금만 더 힘내면 짤 수 있을듯

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

i64 absF(i64 n){
    if(n < 0)
        n *= -1;
    return n;
}


int main() {
    int n;
    scanf("%d", &n);
    vector <int> v(n);
    
    for(int i = 0; i < n; i++){
        scanf("%d", &v[i]);
    }
    
    sort(v.begin(), v.end());
    
    if(v[0] >= 0){
        printf("%d %d", v[0], v[1]);
        return 0;
    }
    if(v[n-1] <= 0){
        printf("%d %d", v[n-2], v[n-1]);
        return 0;
    }
    
    int l=0, r=n-1;
    i64 sum = v[l] + v[r];
    bool goL = true;
    
    while(true){
        if(goL){
            if(v[l+1] < 0)
                l++;
            goL = false;
        }
        if(!goL) {
            if(absF((i64)v[l]+v[l+1]) >= sum){
                if(v[r-1]>=0)
                    r--;
            }
            if(absF((i64)v[l]+v[l+1]) < sum){
                sum = absF((i64)v[l]+v[l+1]);
                goL = true;
            }
        }
        if(l+1 == r)
            break;
    }
    
    printf("%d %d", v[l], v[r]);
    
    return 0;
}

---

dpd??ㅋㅋ

술마셨나? 왜 코드 저렇게 짜놨어

absF((i64)v[l]+v[r]) 이렇게 해야 하는데 왜 l이랑 l+1을 더했지ㅋㅋㅋ 

이것도 수정하고.. 또 가장 작을 때 값 저장을 안 해놔서 따로 저장하는 부분 만들었다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

i64 absF(i64 n){
    if(n < 0)
        n *= -1;
    return n;
}


int main() {
    int n;
    scanf("%d", &n);
    vector <int> v(n);
    
    for(int i = 0; i < n; i++){
        scanf("%d", &v[i]);
    }
    
    sort(v.begin(), v.end());
    
    if(v[0] >= 0){
        printf("%d %d", v[0], v[1]);
        return 0;
    }
    if(v[n-1] <= 0){
        printf("%d %d", v[n-2], v[n-1]);
        return 0;
    }
    
    int l=0, r=n-1;
    int saveL, saveR;
    i64 sum = absF((i64)v[l]+v[r]);
    bool goL = true;
    
    while(true){
        if(goL){
            if(v[l+1] < 0)
                l++;
            goL = false;
        }
        if(!goL) {
            if(absF((i64)v[l]+v[r]) >= sum){
                if(v[r-1]>=0)
                    r--;
            }
            if(absF((i64)v[l]+v[r]) < sum){
                sum = absF((i64)v[l]+v[r]);
                saveL = l;
                saveR = r;
                goL = true;
            }
        }
        if(l+1 == r)
            break;
    }
    
    printf("%d %d", v[saveL], v[saveR]);
    
    return 0;
}

 

음,, 하지만 시간초과

 

l+1 == r 일 떄 break 하도록 했는데 뭔가 예외가 있나 싶어서 l이 음수이고 r이 양수가 아니면 종료되게 코드를 추가했다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

i64 absF(i64 n){
    if(n < 0)
        n *= -1;
    return n;
}


int main() {
    int n;
    scanf("%d", &n);
    vector <int> v(n);
    
    for(int i = 0; i < n; i++){
        scanf("%d", &v[i]);
    }
    
    sort(v.begin(), v.end());
    
    if(v[0] >= 0){
        printf("%d %d", v[0], v[1]);
        return 0;
    }
    if(v[n-1] <= 0){
        printf("%d %d", v[n-2], v[n-1]);
        return 0;
    }
    
    int l=0, r=n-1;
    int saveL, saveR;
    i64 sum = absF((i64)v[l]+v[r]);
    bool goL = true;
    
    while(true){
        if(goL){
            if(v[l+1] < 0)
                l++;
            goL = false;
        }
        if(!goL) {
            if(absF((i64)v[l]+v[r]) >= sum){
                if(v[r-1]>=0)
                    r--;
                else
                    break;
            }
            if(absF((i64)v[l]+v[r]) < sum){
                sum = absF((i64)v[l]+v[r]);
                saveL = l;
                saveR = r;
                goL = true;
            }
        }
        if(l+1 == r)
            break;
    }
    
    printf("%d %d", v[saveL], v[saveR]);
    
    return 0;
}

 

음.. 틀렸..

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

i64 absF(i64 n){
    if(n < 0)
        n *= -1;
    return n;
}


int main() {
    int n;
    scanf("%d", &n);
    vector <int> v(n);
    
    for(int i = 0; i < n; i++){
        scanf("%d", &v[i]);
    }
    
    sort(v.begin(), v.end());
    
    if(v[0] >= 0){
        printf("%d %d", v[0], v[1]);
        return 0;
    }
    if(v[n-1] <= 0){
        printf("%d %d", v[n-2], v[n-1]);
        return 0;
    }
    
    int l=0, r=n-1;
    int saveL = l, saveR = r;
    i64 sum = absF((i64)v[l]+v[r]);
    bool goL = true;
    
    while(true){
        if(goL){
            if(v[l+1] < 0)
                l++;
            goL = false;
        }
        if(!goL) {
            if(absF((i64)v[l]+v[r]) >= sum){
                if(v[r-1]>=0)
                    r--;
                else
                    break;
            }
            if(absF((i64)v[l]+v[r]) < sum){
                sum = absF((i64)v[l]+v[r]);
                saveL = l;
                saveR = r;
                goL = true;
            }
        }
        if(l+1 == r)
            break;
    }
    
    printf("%d %d", v[saveL], v[saveR]);
    
    return 0;
}

아 그 초기화! saveL 초기화 안 했다. 

그래서 초기화 추가했음

 

그래도 틀렸다

 

---

dh..

정렬하고 l=0, r=n-1을 가리킨 다음 합이 0이 되게끔 움직이면 된다. 

l이 앞으로 가면 값이 커지고 r이 뒤로 가면 값이 작아진다는 걸 이용함.. 오.. 와.. 워...

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

i64 absF(i64 n){
    if(n < 0)
        n *= -1;
    return n;
}


int main() {
    int n;
    scanf("%d", &n);
    vector <int> v(n);
    
    for(int i = 0; i < n; i++){
        scanf("%d", &v[i]);
    }
    
    sort(v.begin(), v.end());
    
    int l=0, r=n-1;
    int saveL = l, saveR = r;
    i64 sum = (i64)v[l]+v[r];
    i64 minSum = sum;
    
    while(l+1 != r){
        
        if(sum < 0)
            l++;
        else if(sum > 0)
            r--;
        else {
            saveL = l, saveR = r;
            break;
        }
        
        if(absF(minSum) > absF((i64)v[l]+v[r])){
            saveL = l, saveR = r;
            minSum = (i64)v[l]+v[r];
        }
        sum = (i64)v[l]+v[r];
        
    }
    
    printf("%d %d", v[saveL], v[saveR]);
    
    return 0;
}

증명은? 귀납법.. 

 

농담이고..

 

다른 범위가 왜 안 되는지 증명해서 범위를 줄임 -> 반복 (2개만 남을 때까지)

이런 이유로 이 코드가 돌아간ㄴ다

허어어 잠이 너무 와서 바로 자야겠음