#3273 : 두 수의 합

풀이방법

사용된 것:

정렬

두 개의 포인터(two pointers)

 

2022.03.05

주어진 정수 배열을 일단 오름차순 정렬한다.

그 후 다음과 같은 방법으로 차근차근 합을 살펴본다.

빨간 화살표로 표시된 놈과 파란 화살표로 표시된 놈을 더해보고, 그 합이 X와 동일하면 경우의 수를 1 증가시킨다.

편의를 위해 빨간 화살표로 표시된 수를 앞놈이라고 하고 파란 화살표로 표시된 수를 뒷놈이라고 부르겠다.

 

 

가능한 모든 뒷놈을 다 돌았으면, 앞놈을 바꾸고 다시 뒷놈 순회

---

점검 가능한 마지막 경우의 수는 이 그림과 같다

 

앞놈, 뒷놈의 위치를 각각 가리키는 정수형 변수 두 개(아래의 코드에서는 i와 j)를 사용한다.

이중 반복문을 돌리며 앞에서부터(즉 작은 수부터) 앞놈과 뒷놈의 합을 점검해주면 된다.

 

이 때, 수열을 오름차순 정렬해두었으므로, 앞놈의 값이 이미 X보다 크거나 같은 경우 어떤 뒷놈을 선택하더라도 그 합이 X보다 크다. 우리는 정답에 영향을 줄 수 있는 모든 경우의 수를 이미 다 점검한 것이다. 즉시 외부 반복문을 종료하고 답을 출력한다.

그리고 앞놈과 뒷놈의 합이 X보다 큰 경우에도 우리는 해당 앞놈과 더하여 X를 도출할 가능성이 있는 모든 뒷놈을 이미 다 점검한 것이다. 즉시 내부 반복문을 종료하고 다음 앞놈으로 넘어간다.

 

코드

Java(2022.03.05)

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

public class Main {

	static int n, x, ans;	//수열의 길이, 목표 합, 정답
	static int[] nums;		//수열
	static StringTokenizer st;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//수열의 크기 읽어오기
		n = Integer.parseInt(br.readLine());
		nums = new int[n];
		//수열 읽어오기
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		//목표 합 읽어오기
		x = Integer.parseInt(br.readLine());
		
		//오름차순 정렬
		Arrays.sort(nums);
		//탐색하기
		ans = 0;
		for(int i = 0; i<n-1; i++) {
			if(nums[i] >= x) break;
			for(int j = i+1; j<n; j++) {
				int sum = nums[i] + nums[j];
				if(sum > x) break;
				else if(sum == x)ans++;
			}
		}
		System.out.print(ans);
	}

}