[백준/Java] 1253번 - 좋다

문제

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

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

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

입력

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

출력

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

 
 

- 문제 풀이 방법

https://allyouredreaminof.tistory.com/57

[백준/Java] 1940번 - 주몽

이 문제와 동일한 방식을 사용하여 문제를 풀면 된다. 
정렬한 배열의 양 끝을 i, j로 투 포인터를 설정해준다. 
단, 배열의 원소 각각을 기준으로 while문을 실행한다. 
또한, 기준값(원소 자기 자신)은 좋은 수 만들기에 포함되면 안 된다는 점을 고려하여 코드를 작성한다. 
즉, 기준값의 인덱스가 k이며 arr[k] = arr[i] + arr[j] 일 때, k는 i, j가 될 수 없다.
 
 

- 코드

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[] arr = new int[N];
		
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr);

		int cnt = 0;
		
		for (int k = 0; k < N; k++) {
			int i = 0; 
			int j = N - 1;
			int find = arr[k];
			
			while (i < j) {
				int sum = arr[i] + arr[j];
				
				if (sum < find) {
					i++;
				}
				else if (sum > find) {
					j--;
				}
				else {
					if (i != k && j != k) {
						cnt++;
						break;
					}
					else if (i == k) {
						i++;
					}
					else if (j == k) {
						j--;
					}
				}
			}
		}
		System.out.println(cnt);
		
		sc.close();
	}

}

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

1253번: 좋다