백준 1940번 <주몽>

백준 알고리즘 1940번

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

1940번: 주몽

---

1940번

갑옷은 두 개의 재료로 만드는데 두 재료의 고유 번호를 합쳐서 M이 되면 값옷을 만들 수 있다.

N개의 재료와 M이 주어졌을 때, 몇 개의 갑옷을 만들 수 있는지 구하여라.

 

입력으로 첫 줄에 재료의 개수 N이 주어지고 두 번째 줄에 M이 주어진다. 마지막 줄에 N개의 고유 번호가 주어진다.

 

출력으로 만들 수 있는 갑옷의 수를 출력하면 된다.

---

문제 해결

이진 탐색으로 문제를 해결했다.

재료는 각각 고유한 번호를 가지고 있고 갑옷을 만드는데 2개의 재료가 필요하다.

따라서 M을 만들 수 있는 쌍을 이루는 재료의 교유한 번호는 중복되지 않는다.

 

각 재료의 고유한 번호를 기준으로 이진 탐색을 하는데 이때 찾는 데이터는 M - 고유 번호이다.

중복으로 찾는 경우를 방지하기 위해 visit 배열을 통해 이미 찾은 쌍의 고유 번호를 표시해 두었다.

---

코드

package bj1940;

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

public class Main {
	static int[] num;
	static boolean[] visit;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		String[] inArr = br.readLine().split(" ");
		if (N == 1) {
			System.out.println(0);
			System.exit(0);
		}
		visit = new boolean[N];
		num = new int[N];
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(inArr[i]);
			visit[i] = false;
		}

		int answer = 0;
		Arrays.sort(num);

		for (int i = 0; i < N; i++) {
			if (visit[i]) {
				continue;
			}
			int a = BS(0, N - 1, M - num[i]);
			if (a == i) {
				continue;
			}
			if (a != -1) {
				if (visit[a]) {
					continue;
				}
				visit[i] = true;
				visit[a] = true;
				answer++;
			}
		}
		System.out.println(answer);

	}

	public static int BS(int start, int end, int data) {
		int answer = -1;
		while (start <= end) {
			int mid = (start + end) / 2;
			if (num[mid] > data) {
				end = mid - 1;
			} else if (num[mid] == data) {
				return mid;
			} else {
				start = mid + 1;
			}
		}
		return answer;
	}

}

---

결과

---