[백준 1940] 주몽

😊 문제

백준 1940 - 주몽

😊 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(bf.readLine()); // 재료의 개수
		int M = Integer.parseInt(bf.readLine()); // 갑옷을 만드는데 필요한 수

		StringTokenizer st = new StringTokenizer(bf.readLine());
		int c[] = new int[N]; // 갑옷 재료 고유 번호 clothes

		for (int i = 0; i < N; i++) {
			c[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(c);

		int cnt = 0; // 만들어지는 갑옷 수
		int start = 0;
		int end = N - 1;

		while (start < end) {
			if (c[start] + c[end] > M) {
				end--;
			} else if (c[start] + c[end] < M) {
				start++;
			} else { // (c[start]+c[end] == M)
				cnt++;
				start++;
				end--;
			}
		}

		System.out.println(cnt);

	}

}

😊 풀이

갑옷을 1개를 만들기 위해서 2가지 재료의 고유한 번호의 합이
갑옷 1개를 만드는데 필요한 수와 일치하면 되는 문제

2개의 재료를 합한 값 = 갑옷을 만드는데 필요한 수 M

N값을 오름차순으로 정렬해 준 후 첫번째 값과 가장 끝값에 포인터 start, end를 위치 시킨 후
포인터 이동 원칙을 이용해 풀이해주었습니다.

c[start] + c[end] > M : end — : 두 재료의 합이 M보다 크다면 큰 값의 index 위치 -1
c[start] + c[end] < M : start++ : 두 재료의 합이 M보다 작다면 작은 값의 index 위치 +1
c[start] + c[end] == M : cnt++, start++, end— : 두 재료의 합이 M보다 같다면 갑옷 완성 개수 +1, 작은 값의 index 위치 +1, 큰 값의 위치 -1