[백준] 1940 주몽 - Java

 

 

 

문제 출저

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

1940번: 주몽

 

 

 

문제 풀이

재료들의 번호가 주어집니다. 재료들의 고유 번호를 합쳐서 M이 되는 경우의 수를 구해야 합니다. 

 

두 포인터를 이용해 풀었습니다. 

재료들을 정렬합니다. start, end 두 개의 포인터를 사용합니다.

start는 배열의 시작, end는 배열의 끝에서 시작합니다. 

두 개의 합을 합쳐서 M 보다 작으면 start를 올리고 M보다 크면 end를 줄입니다.

 

 

소스코드

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

/*
주몽
https://www.acmicpc.net/problem/1940
 */

public class Main {

    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());
        int[] boards = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        Arrays.sort(boards);

        int start = 0;
        int end = n-1;
        int answer = 0;

        while(start < end) {
            int result = boards[start] + boards[end];
            if(result == m) {
                answer++;
                end--;
            }

            if(result > m) {
                end--;
            }
            else {
                start++;
            }
        }

        System.out.println(answer);

    }
}