[백준_1253번] 좋다

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

1253번: 좋다

[문제]

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

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

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1253 {
	static int[] num;
	static int count=0,n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		num=new int[n];
		
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();
		
		Arrays.sort(num);
		
		for(int i=0;i<n;i++) {
			int start=0, end=n-1;
			int target=num[i]; // 두 수를 더한 값의 결과가 되야하는 값
			
			while(start<end) {
				int sum=num[start]+num[end]; // 두 수를 더한 값이
				
				// target 보다 작다면 시작 포인트 증가
				if(sum<target)
					start++;
				// target 보다 크다면 끝 포인트 감소
				else if(sum>target)
					end--;
				else { // target과 같고
					// 두 포인트가 i번째 수가 아니라면 count 증가
					if(i!=start&&i!=end) {
						count++;
						break;
					}
					// 두 포인트중 i번째 수가 나오면 안되기 때문에 처리
					if(start==i)
						start++;
					if(end==i)
						end--;
				}
			}
		}
		System.out.println(count);
		
	}

}

 

[고찰] 

 이번 문제는 투포인터를 사용해야 하는 문제로 정렬된 배열에 start, end 두 개의 포인터를 조건에 따라 알맞게 이동시켜 주면 되는 문제였다. 두 포인터중 i번째 수가 나오면 안된다는 조건을 주의한다면 어렵지 않은 문제였다.