[Baekjoon 백준] 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보다 작거나 같은 자연수이다.

 

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

---

1. 변수 선언

2. 주어진 수 배열에 저장

3. N 값에 따라 포인터 조정 후 계산

 

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()); // 제시된 재료의 수(1 ≤ M ≤ 10,000,000)
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken()); // 제시된 합(1 ≤ N ≤ 10,000,000)
		int A[] = new int[N];

		st = new StringTokenizer(br.readLine()); 
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken()); 
		}
		 
		int count = 0; // 개수 
 
        for(int startIndex=0; startIndex<N; startIndex++)  {
            int sum = 0;
            int endIndex = startIndex+1;
            while (endIndex<N) { //재료의 수 보다 작을때만
                sum = A[startIndex]; 
                sum += A[endIndex++];
                if (sum == M) {
                	count++;
                    break;
                }
            }

        } 
		System.out.println(count);
}

 

투 포인터로 접근할 수 있는 문제였다.

배열을 오름차순으로 정렬시키고 두 포인터를 양쪽 끝에 위치시킨 후 아래 처럼 이동시키는 로직으로 만들어도 될 것 같다.

 

A[i] + A[j] > M : j--;

A[i] + A[j] < M : i++;

A[i] + A[j] == M : i++; j--; count++;