백준 1940. 주몽

문제 1940. 주몽

문제

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

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

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

풀이

재료들이 무작위로 나열되어 입력된다. 그리고 우리는 나열된 값들 중 2개의 재료의 합이 M이 되는지를 구해야한다.
무작위 나열된 값들로 2개의 합을 구하려면 완전탐색을 해야해서 시간초과가 날 것이다.
그러므로 우선 입력된 값들을 정렬해준다.
정렬하고 첫번째 값을 start로, 두번째 값을 end로 두었다. end를 증가시키면서 start가 가르키는 값과 연산을 하여 M이 되는지를 찾아나갔다. m보다 작으면 end를 하나씩 증가시켜서 마지막 수까지 진행시키고, m보다 크면 start를 하나 증가시키고 end는 start+1로 두었다.

그리고 조건에 재료의 개수 N이 1이상이라길래 N이 1이 될 수 있는 경우를 생각하여 따로 조건문을 두었다.
내 풀이는 이러한데, 책에서 나와있는 풀이는 end를 정렬된 수의 가장 마지막에 두고 end를 줄여가고, start를 증가시키면서 값을 찾아나갔다. 이 풀이가 조금 더 시간을 줄이고 효율적인 풀이인 것 같다.

풀이 코드 java

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

public class boj1940 {
    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());
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
        }
        Arrays.sort(arr);
        int start = 0;
        int end = 1;
        int result = 0;

        if (n == 1) {
            System.out.println(0);
        }
        else {
            while (start < n-1) {
              if (arr[start] + arr[end] < m) {
                    end++;
                    if (end == n) {
                        start++;
                        end = start+1;
                    }
                }
                else if (arr[start] + arr[end] > m) {
                    start++;
                    end = start+1;
                }
                else {
                    result++;
                    start++;
                    end = start+ 1;
                }
            }
            System.out.println(result);
        }
    }
}