백준 JAVA11 1940번 : 주몽

주몽

백준 1940 상세보기

문제

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

Flow.

• 재료 2개의 합으로 M을 충족하는 조합을 찾는다.
• 단순히 재료 2개의 합으로 갑옷을 만듬으로 정렬과 투 포인터를 사용해서 풀 수 있다.
• 재료를 오름차순으로 정렬해준다.
• startIndex 와 endIndex를 움직이면서 M을 충족하는 조합을 카운팅해준다.

package twoPointer;

import java.util.Arrays;
import java.util.Scanner;

public class P1940_joomong {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 6 재료의 개수
		int M = sc.nextInt(); // 9 갑옷 완성 필요치

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

		long cnt = 0;

		int startIndex = 0;
		int endIndex = A.length - 1;

		while (startIndex < endIndex) {
			if (A[startIndex] + A[endIndex] > M) {
				endIndex--;
			} else if (A[startIndex] + A[endIndex] < M) {
				startIndex++;
			} else {
				cnt++;
				startIndex++;
				endIndex--;
			}
		}
		System.out.println(cnt);
	}

}