백준 1253 c++ and java

문제

 

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 1 복사

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1 복사

8

힌트

3,4,5,6,7,8,9,10은 좋다.

 

이 문제는 투포인터 또는 이분탐색으로 풀 수 있었다.

 

문제의 로직

1. 각 자리수를 기준점으로 잡는다.

2. 그 자리수를 제외하고 두개의 수를 더했을때 그 값과 같아지는 갯수를 센다. (이분탐색)

3. 정답을 출력한다.

 

+ l과 r이 i와 같다면 그 자리수를 제외하는 조건이 충족되지 않기 때문에 continue를 해준다.

 

 

c++

#include<bits/stdc++.h>
using namespace std;


int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    int ans = 0;
    cin >> n;
    vector<int>v;

    for(int i = 0 ; i < n ; i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());


    for(int i = 0 ; i < n ; i++){
        int l =0;
        int r = n-1;

        while(l<r){

            if(l==i){l++;continue;}
            if(r==i){r--;continue;}
            if(v[i]>v[l]+v[r]){l++;continue;}
            if(v[i]<v[l]+v[r]){r--;continue;}
            else{ans++;break;}
        }
    }
    cout << ans <<"\n";



    return 0;
}

 

java

import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int n = Integer.parseInt(s);

        Vector<Integer> v = new Vector<Integer>();


        StringTokenizer st = new StringTokenizer(br.readLine());


        for(int i = 0 ; i < n ; i++){
            if(st.hasMoreTokens()){
                int temp = Integer.parseInt(st.nextToken());
                v.add(temp);
            }
        }

        Collections.sort(v);

        int ans = 0;

        for(int i= 0 ;i < n; i++){
            int l = 0;
            int r = n-1;

            while(l<r){
                if(l==i){l++; continue;}
                if(r==i){r--; continue;}
                if(v.get(i) > v.get(l)+v.get(r)){l++;continue;}
                if (v.get(i) < v.get(l)+v.get(r)){r--;continue;}
                if(v.get(i) == v.get(l)+v.get(r)){ans++;break;}
            }

        }

        System.out.println(ans);

    }
}