백준 1253번

 

문제

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

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

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

입력

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

 

 

처음 제출한 코드, 틀렸다고 떴다 ..! 

 

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

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

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int n = Integer.parseInt(st.nextToken());
        long [] arr = new long[n];
        long count=0;

        //주어진 n개의 수에서 두수의 합으로 표현되는 수를 찾아야 한다.
        //n : 수의 개수
        // m :배열 수

        //for문으로 가능할 것 같고
        //while도 가능할 것 같다.

        //for(1번 idx에서 끝까지 돈다.)
        //2번 idx에서 끝까지 돈다.
        st = new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        //n개 중에 다른 두수의 합으로 표현되는 수가 있다면 그 수를 좋은수 라고 한다.
        //좋은 수 가 총 몇개 일까 ?
        //오름차 순으로 정렬해준다.
        //1일때 맞는 숫자 -> 찾아줌
        //2일때 맞는 숫자 -> 찾아줌
        //3일때 맞는 숫자 -> 찾아줌
        //근데 더하는 수는 서로 다른 수어야 한다.
       //본인은 제외하도록 해야 한다. 

        int start_idx=0;
        int end_idx=1;
        long find=0;
        for(int i=0;i<n;i++){
            find = arr[i];
            start_idx =0;
            end_idx=n-1;
            while(start_idx<end_idx){
                if(arr[start_idx]+arr[end_idx]==find){
                    if(start_idx!=end_idx){
                        count++;
                        break;
                    }
                    else if(start_idx==i){ //본인을 제외 하기 위해서 
                        start_idx++;
                    } 
                    else if(end_idx==i){ //본인을 제외하기 위해서 
                        end_idx--;
                    }
                }
                else if(arr[start_idx]+arr[end_idx]<find){
                    start_idx++;
                }
                else{
                    end_idx--;;
                }
            }
        }




        System.out.println(count);

        bf.close();






    }
}

 

 

성공!! 

 

1. 두수의 합을 구할때, 두 수 다 본인이 포함되지 않는 경우를 count해야 한다. 

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

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

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int n = Integer.parseInt(st.nextToken());
        long [] arr = new long[n];
        long count=0;

        //주어진 n개의 수에서 두수의 합으로 표현되는 수를 찾아야 한다.
        //n : 수의 개수
        // m :배열 수

        //for문으로 가능할 것 같고
        //while도 가능할 것 같다.

        //for(1번 idx에서 끝까지 돈다.)
        //2번 idx에서 끝까지 돈다.
        st = new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        //n개 중에 다른 두수의 합으로 표현되는 수가 있다면 그 수를 좋은수 라고 한다.
        //좋은 수 가 총 몇개 일까 ?
        //오름차 순으로 정렬해준다.
        //1일때 맞는 숫자 -> 찾아줌
        //2일때 맞는 숫자 -> 찾아줌
        //3일때 맞는 숫자 -> 찾아줌
        //근데 더하는 수는 서로 다른 수어야 한다.
       //본인은 제외하도록 해야 한다.

        int start_idx=0;
        int end_idx=1;
        long find=0;
        for(int i=0;i<n;i++){
            find = arr[i];
            start_idx =0;
            end_idx=n-1;
            while(start_idx<end_idx){
                if(arr[start_idx]+arr[end_idx]==find){
                    if(start_idx!=i && end_idx!=i){
                        count++;
                        break;
                    }
                    else if(start_idx==i){ //본인을 제외 하기 위해서
                        start_idx++;

                    }
                    else if(end_idx==i){ //본인을 제외하기 위해서
                        end_idx--;
                    }
                }
                else if(arr[start_idx]+arr[end_idx]<find){
                    start_idx++;
                }
                else{
                    end_idx--;;
                }
            }
        }




        System.out.println(count);

        bf.close();






    }
}