[JAVA/백준] 1253번 : 좋다(GOOD)

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

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

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

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

<Output>

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

<examples>
-입력

10
1 2 3 4 5 6 7 8 9 10

-출력

8

 

[풀이]

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P1253_좋은수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Long A[] = new Long[N];
        int count = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0;i<N;i++){
            A[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(A);
        for (int k =0;k<N;k++){
            long find = A[k];
            int i = 0;
            int j = N-1;

            while (i<j){
                if (A[i] + A[j] == find){ //(1)
                    if (i!=k && j !=k){ //자기 자신을 좋은 수에 포함하면 안됨..(1,k) 안됨
                        count++;
                        break; //if문은 여기서 break; (2)로 갑니다.
                    } else if (i == k) {
                        i++; 
                    } else if (j == k) {
                        j--; 
                    }
                }else if (A[i] + A[j] < find){ //(2) 
                   i++; 
                }else {
                    j--; 
                }
            }
        }
        System.out.println(count);
        br.close();

    }
}

 

---

 

투 포인트를 양 끝단에 두고 좁혀 나가며 좋은 수를 카운트하기!

이 문제는 배열을 하나씩 돌며, 그 안에서 반복문을 돌려가며 

원소 하나, 하나씩 좋은 수를 찾아줘야한다는 것이다. (해당 원소를 만들어주는 두 수의 조합을 찾아야 함)

서로 다른 두 수의 조합이야하기 때문에 두 포인트가 만나면 안되고 역전 되기 전까지만 조회를 해야한다.

또 자기 자신을 포함할 수 없다는 점도 유의하여 짜도록 하자...