백준 2473 세 용액

바로 이전에 푼 문제보다 조금 쉬운 문제이다. 저번 문제는 3명의 합이 0인 개수를 구하는 문제였고, 이번에는 합의 절대값이 최소인 것만 찾으면 된다. 정말 간단하다.

투 포인터 방향은 쉽게 잡았다. 문제도 유사해서 문제에서 제공하는 테스트케이스는 돌아가게 쉽게 만들었다.

 

문제는, 악마는 디테일에 있다는 것. 생각없이 int로 만든것을 보고 long long으로 바꿨다. 그래도 특정 %에서 틀렸습니다가 나왔다.

문제질문 보면 다양한 사례가 있더라. int - long long 범위 문제도 많았고, 중간에 특성값 계산할때 절대값 연산을 하는게 편한데 그때 abs() 함수에서 문제가 발생한 사례도 있었다. 컴파일러 구현체마다 std::abs가 아닌 그냥 abs를 int abs(int , int) 이렇게 받을때도 있더라... 저런걸로 틀리면 진짜 정신나갈것 같다.

어떻게 어떻게 찾아보니 문제를 발견했다.

 

처음 구현시, 현재 특성값보다 절대값이 낮은것을 찾게 되면 해당 조합으로 업데이트하고 L을 한칸 밀었는데, 그러면 안됬었다. 현재 값의 부호에 따라 R이 밀릴수도 L이 밀릴수도 있는데, 무작정 L을 밀어버려 탐색할 수 있는 범위를 탐색하지 않았던 것이 문제가 됐다. 

조합을 업데이트했을때, LR을 인위적으로 움직이지 않고, 현재 특성값의 부호에 따라 계속 탐색을 하도록 작성했다.

 

조합은 Vector에 넣어 출력 전에 한번 그냥 정렬해줬다. 문명의 이기를 쓰는것이 행복하다...

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>

std::ostream& operator<<(std::ostream& os, std::vector<long long> vec)
{
    for (int i = 0; i < vec.size(); i++)
        os << vec[i] << " ";
    // os << '\n';
    return os;
}

int main()
{
    int N;
    std::cin >> N;
    std::vector<long long> solutions;
    std::vector<long long> answer;
    long long phABS = 40000000000;

    for (int i = 0 ; i < N; i++)
    {
        long long temp;
        std::cin >> temp;
        solutions.push_back(temp);
    }
    std::sort(solutions.begin(), solutions.end());
    for (int i = 0; i < N - 2; i++)
    {
        long long curSol = solutions[i];
        int L = i + 1;
        int R = N - 1;

        while (L < R)
        {
            // if (L == i || R == i)
            // {
            //     if (L == i)
            //         L++;
            //     if (R == i)
            //         R--;
            //     continue;
            // }
            long long mixture = curSol + solutions[L] + solutions[R];

            if (std::abs(mixture) < phABS)
            {
                phABS = std::abs(mixture);
                answer.clear();
                answer.push_back(curSol);
                answer.push_back(solutions[L]);
                answer.push_back(solutions[R]);
                // L++; 이 부분이 문제. 이때 찾았다고 넘기면 안되었다...
            }
            if (mixture < 0)
            {
                L++;
            }
            else
            {
                R--;
            }
        }
    }
    std::sort(answer.begin(), answer.end());
    std::cout << answer;
}

 

저번 문제 와 진짜 유사해서 오래 걸리지 않았다. 중간에 오류나서 조금 당황하긴 했는데 테케 계속 넣어보고 하면서 탐색을 해 나갔다. 틀렸더라도 당황하지 않고 코드를 찬찬히 보는 습관이 필요하다.

 

오늘도 평온한 하루가 되길. 슨민.