[C++/BOJ] 13423 : Three Dots (이진탐색) / 삽질 기록

https://www.acmicpc.net/problem/13423

문제

직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 Xa, Xb, Xc이다. 이때 점 a, b 사이의 거리와 점 b, c사이의 거리가 같으면 세 점의 간격이 같다고 한다. 즉, Xb - Xa = Xc – Xb일 때 세 점의 간격이 같다. 다음은 N = 5인 경우의 예시이다.

위 예시에서 점의 위치는 각각 -4, -1, 0, 2, 4이다. 이중 -4, -1, 0위치의 세 점을 각각 a, b, c라고 하면 Xb - Xa = 3, Xc – Xb = 1로 간격이 같지 않다. 그러나 -4, -1, 2 위치의 세 점을 각각 a, b, c라고 하면 Xb - Xa = 3, Xc – Xb = 3으로 세 점의 간격이 같다. 위 예시에서 간격이 같은 세 점 a, b, c로 가능한 경우는 (-4, -1, 2), (-4, 0, 4), (0, 2, 4)의 3가지가 있다. N개의 점의 위치가 주어졌을 때, 간격이 같은 세 점으로 가능한 경우가 모두 몇 가지 있는지 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,000)이 주어진다. 테스트 케이스의 둘째 줄에는 N개의 점의 위치 X1, X2, X3 … Xn이 차례로 주어진다. 모든 점의 위치는 -100,000,000이상 100,000,000이하의 정수이다.

출력

각 테스트 케이스의 답을 순서대로 출력한다. 각 테스트 케이스마다 첫째 줄에 간격이 같은 세 점 a, b, c로 가능한 경우의 수를 출력한다.

---

실버2 맞냐..?

솔직히 더 높게 쳐줘야함

예전에 완탐으로 풀다가 장렬하게 실패한 문제인데, 이번주에 코알라 스터디에서 이분탐색 다루길래

다시 풀어보았다!

 

보통은 접근방법이

left와 right 인덱스 지정해서 가운데 값을 찾는 식으로 접근하는데,

 

나는 middle 값을 먼저 지정해주고, left 간격과 right 간격을 이용해서 탐색을 해주었다. 이것도 이분탐색인가..?

어쨌든 난 이 풀이가 더 편했음!

 

정렬은 필수!

사실 이거 리스트 처음에 vector로 안하고 걍 int형 배열로 1001크기 선언해서 했단 말이지

근데 그걸 정렬하면 -4, -1,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...이딴식으로 되는데

그걸 발견못해서 몇 분 정도 헤멨다 맞왜틀

^^...

 

 

 

나의 풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    int n;

    cin >> t;
    for (int i = 0; i < t; ++i){
        vector<int> dots;
        int dot;
        cin >> n;
        for (int j = 0; j < n;++j){
            cin >> dot;
            dots.push_back(dot);
        }
        sort(dots.begin(), dots.end());

        int cnt = 0;
        for (int m = 1; m < n-1; ++m){
            int left = 0;
            int right = n - 1;
            while(left<right){
                if(left==m || m==right) break;
                
                int l_to_m = dots[m] - dots[left];
                int m_to_r = dots[right] - dots[m];
                
                if(l_to_m == m_to_r) {
                    cnt++;
                    left++;
                }
                else if(l_to_m > m_to_r) left++;
                else right--;
            }
        }
        cout << cnt << "\n";
    }
}

 

그나저나 알고리즘 잔디찍던 깃허브 레포가 터져버렸는데,,, 500

조졌군

빠른 복구 기원

 

그리고 요즘 블로그 수익이 적지만 은근 짭짤해서 기분이 좋다

티스토리 최고!