[JAVA]백준 1940번: 주몽

 

www.acmicpc.net/problem/1940

1940번: 주몽

 

1. 문제 설명

 

N개의 재료가 주어지고 재료 중 2개를 합쳐서 M이 되는 재료의 쌍의 개수를 구하는 문제이다.

 

2. 코드

 

간단한 방식으로 푼 코드이다. 최대 입력 가능한 범위까지 boolean 배열을 만들고 boolean [재료]를 true로 설정한다. 그 후 한 재료와 합쳐져서 M이 될 수 있는 재료의 boolean 값이 true인지 false인지 확인한다.

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {


    public static boolean[] material_list=new boolean[200001];

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        int material_num=scan.nextInt();
        int material_need=scan.nextInt();

        int sum=0;
        
        if(material_need>200000){
            System.out.println("0");
            scan.close();
            return;
        }

        for(int i=0;i<material_num;i++){
            int temp=scan.nextInt();
            material_list[temp]=true;
        }

        for(int i=1;i<=200000;i++)
        {
            if(material_list[i] && material_need>i){
                if(material_list[material_need-i])
                    sum++;
            }

        }

        System.out.println(sum/2);

        scan.close();
    }


}

 

 

정석대로 푼 방식이라고 생각된다. 이분탐색과 비슷한 접근방법이다.

재료들의 array를 정렬하고 start=0,end=재료의 마지막에서 시작한다.

start와 end의 값을 합해 M과 같다면 답의 개수를 증가한다.

start와 end의 값이 M보다 작다면 더 큰 값을 더해야 하므로 start를 증가시킨다.

start와 end의 값이 M보다 크다면 수를 줄여야 하므로 end를 감소시킨다.

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {




    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        int material_num=scan.nextInt();
        int material_need=scan.nextInt();

        int[] material_list=new int[material_num];

        int sum=0;

        if(material_need>200000){
            System.out.println("0");
            scan.close();
            return;
        }

        for(int i=0;i<material_num;i++)
            material_list[i]=scan.nextInt();


        Arrays.sort(material_list);


        int start=0,end=material_num-1;

        while(start<end){

            int temp=material_list[start]+material_list[end];
            if(temp==material_need){
                sum++;
                start++;
                end--;
            }else if(temp<material_need){
                start++;
            }else{
                end--;
            }
        }

        System.out.println(sum);

        scan.close();
    }


}