[백준] 1940번 - 주몽(Java)(○)

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

1940번: 주몽

 

<입력범위>

N : 재료의 수 : 1 ~ 15,000

M : 갑옷 필요한 재료의 수 : 1 ~ 10,000,000

 

<풀이>

1. 재료 번호 중 2개의 합이 M이 되면 갑옷이 완성된다.

2. DFS로 풀기에는 N이 너무 크다.

3. 투 포인터로 sIdx는 앞에서, eIdx는 뒤에서부터 진행하면서 합산한다.

 

 

<구현>

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

public class Main {
    static int N, M;
    static int A[];
    
	void Solve() {
        int count = 0;
        Arrays.sort(A);
        // sIdx는 처음부터, eIdx는 마지막부터 시작
        int sIdx = 0, eIdx = N-1;
        while (sIdx < eIdx) {
            int sum = A[sIdx] + A[eIdx];
            if (sum == M) { // M을 찾으면 두 인덱스 모두 변경
                count++;
                sIdx++;
                eIdx--;
            } else if (sum < M) { // M보다 작으면 더 큰 값이 필요함
                sIdx++;
            } else { // M 보다 크면 더 작은 값이 필요함
                eIdx--;
            }
        }
        System.out.println(count);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        //StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }

}