[1940] 주몽 (JAVA)

# 문제 설명

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 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보다 작거나 같은 자연수이다.

---

출력

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

 

# 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[] arr = new int[N]; //재료 번호 배열

        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++) {
            arr[n] = Integer.parseInt(st.nextToken());
        }

        int n1 = 0;
        int n2 = 1;
        int cnt = 0;

        while (n1 < arr.length - 1) {
            if (arr[n1] + arr[n2] == M) {
                cnt++;
            }

            if (n2 == N - 1) {
                n1++;
                n2 = n1 + 1;
            }
            else {
                n2++;
            }
        }

        System.out.println(cnt);
    }
}

 

두 재료 번호의 합이 갑옷을 만드는데 필요한 수 M과 같으면 갑옷을 만들 수 있다.

 

N, M, 재료 번호 배열 arr을 입력받는다.

cnt로 만들 수 있는 갑옷 수를 저장한다.

그 다음 arr의 인덱스를 가리키는 n1, n2 포인터를 만든다.

n1은 0, n2는 1로 설정했는데 이는 n1을 기준으로 n2를 움직여가며 M과 같은지 검사를 하기 위해서이다.

 

n1이 arr 배열의 끝에 도달할 때까지 반복한다.

만약 arr[n1]과 arr[n2]의 합이 M과 같으면 cnt를 1 증가한다.

n2가 arr의 끝(N-1)과 같으면, n1을 1 증가하고 n2는 n1의 오른쪽(n1 + 1)으로 설정한다.

아직 n2가 arr의 끝까지 가지 않았으면, n2를 1 증가한다.