백준 3151 합이 0

오늘은 좀 쉬운거 잡고 오전에 다른거 해야지 했는데 예상보다 날 많이 괴롭혔다 이 문제가.

투 포인터를 사용하는 나쁘지 않은 편한 문제이다. 처음 보았을 때 정렬을 해두고 어떤 한 원소를 고정해두고 나머지 원소들을 투 포인터로 탐색하며 조합을 찾으면 좋겠다고 생각했다.

 

처음에는 선정한 한 개를 빼고 나머지들에서 투 포인터 탐색을 구현했다. 그렇게 되니 막 중복으로 찾고 난리가 나더라. 다시 생각해보니 어떤 원소 하나를 정하고 그 다음것부터 마지막까지만 계산하면 되는 문제였다.

 

그렇게 짜고 나니, 같은 값의 원소가 많이 있을 수 있다는 점이 걸렸다. L과 R이 가르키는 원소가 조합을 만족할 때, 우리는 두가지 상황에 빠진다.

하나는 두 원소가 값이 같을 경우. 이 때는 해당 값이 몇개 있는지 확인하고, k 개가 있다면 kC2를 구한다(R - L + 1 = k)

두 번째는 두 원소가 값이 다를경우, 이때는 각 값이 몇개 있는지 확인하고 두 값의 개수를 곱하면 조합의 개수가 나온다.

만약 첫번째 경우일경우, 더이상 탐색하는것이 의미가 없으므로 값을 구하고 break한다.

이 외에는 현재 조합이 0보다 클경우 조합의 값을 줄이기 위해 R을 1 감소하고, 그 반대의 경우 L을 1 증가시키며 탐색을 반복한다.

 

처음 이 접근이 시간초과가 나오지 않을까? 했는데 시간제한이 다른 문제들보다 넉넉한 편이라 괜찮겠지... 하고 짰다.

---

#include <iostream>
#include <vector>
#include <algorithm>



// std::ostream& operator<<(std::ostream& os, std::vector<int> 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<int> stdList;
    long long cnt = 0;

    for (int i  = 0; i < N ; i++)
    {
        int student;
        std::cin >> student;
        stdList.push_back(student);
    }  

    std::sort(stdList.begin(), stdList.end());
    // std::cout << stdList;
    
    for (int i = 0; i < N - 2; i++)
    {
        int l = i+1;
        int r = N - 1;
        int cur = stdList[i];
        if (cur > 0)
            break;
        while (l < r)
        {
            int curLvl = cur + stdList[l] + stdList[r];
                // 중복된 것 체크
            if (curLvl == 0)
            {
                if (stdList[l] == stdList[r])
                {
                    cnt += (int)((r - l + 1) * (r - l)) / 2;
                    break;
                }
                else
                {
                    int rStart = stdList[r];
                    int rCnt = 0;
                    while (1)
                    {
                        if (stdList[r] != rStart)
                            break;
                        else
                        {
                            r--;
                            rCnt++;
                        }
                    }
                    int lStart = stdList[l];
                    int lCnt = 0;
                    while (1)
                    {
                        if (stdList[l] != lStart)
                            break;
                        else
                        {
                            l++;
                            lCnt++;
                        }
                    }
                    cnt += (lCnt * rCnt);
                }
            }
            else if (curLvl > 0)
                r--;
            else
                l++;
        }
        
        
    }
    std::cout << cnt << '\n';
}

이걸 돌아가게 짠건 1시간? 정도 걸렸는데 계속 27%에서 틀려서 몇시간을 더 본것 같다.

같은 로직으로 짠 파이썬도 돌려봤는데 그건 PASS... 진짜 미춰버리는줄 알았다.

문제는 조합의 개수를 세는 cnt 변수가 int 였던것이다. 아니 그렇게 조합이 많을줄은 몰랐지... 에휴...

long long으로 바꾸니 잘 돌아간다... 하하... 오늘은 이거 보다가 허허... 했다.

넓게 보는 습관이 필요하다... 하하

 

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