[백준] 18114번: 블랙 프라이데이

조소복·2022년 12월 22일

Java 골드V 백준 자바

문제

서강 백화점이 블랙 프라이데이를 맞아서 특별 이벤트를 진행한다. 백화점에서 제시하는 양의 정수의 무게 C에 딱 맞게 물건들을 가져오면 전부 만 원에 판매하는 이벤트이다.

선택할 수 있는 물건은 최대 3개까지이고, 같은 물건을 중복 선택하는 것은 불가능하다. 그리고 백화점에서 판매하는 물건들의 무게는 모두 다르다.

예를 들어, 백화점에서 판매하고 있는 물건 5개의 무게가 각각 1, 2, 3, 4, 5일 때, C가 5라면 {2, 3} 또는 {5}에 해당하는 물건의 조합을 만 원에 구매할 수 있다.

판매하는 물건 N개의 양의 정수의 무게가 각각 주어질 때, 만 원에 구매할 수 있는 조합이 있는지 출력하라.

입력

첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ $10^8$ , N과 C는 양의 정수)

다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진다. (1 ≤ w ≤ $10^8$ , w는 양의 정수)

출력

문제의 조건을 만족하는 조합이 있으면 1, 그렇지 않으면 0을 출력한다.

예제 입력 1

5 5
1 2 3 4 5

예제 출력 1

예제 입력 2

3 13
3 7 8

예제 출력 2

문제 풀이

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

public class BJ18114 {
    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());
        long C=Integer.parseInt(st.nextToken());

        long[] weight=new long[(int)N];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            weight[i]=Long.parseLong(st.nextToken());
        }

        Arrays.sort(weight);

        // 최대 물건 3개
        for(int i=0;i<N;i++){

            // C에 맞는 경우
            if(weight[i]==C){
                System.out.println(1);
                System.exit(0);
            }
            for(int j=i+1;j<N;j++){
                // C에 맞는 경우
                if(weight[i]+weight[j]==C){
                    System.out.println(1);
                    System.exit(0);
                }

                // 나머지 하나 탐색
                int left=0;
                int right=N-1;
                while(left<=right){
                    int mid=(left+right)/2;

                    if(weight[i]+weight[j]+weight[mid]==C){
                        if(mid!=i && mid!=j) {
                            System.out.println(1);
                            System.exit(0);
                        }
                    }

                    if(weight[i]+weight[j]+weight[mid]>C){
                        right=mid-1;
                    }
                    else{
                        left=mid+1;
                    }
                }
            }

        }
        System.out.println(0);

    }
}

문제에서 물건을 최대 3개까지만 선택할 수 있도록 제한해두었기 때문에 조금 더 편하게 코드를 짤 수 있다.

먼저 물건 하나를 선택한 후, C 무게인지 확인하고 맞다면 1을 출력한다.

그게 아니라면 다음 물건 하나를 또 선택한 후 두 물건의 합이 C인지 확인하고 맞다면 1을 출력, 아니라면 나머지 하나를 탐색한다.

이때, 이분탐색을 이용하여 물건을 찾게된다.

나머지 하나의 물건을 찾아서 처음에 선택한 물건 두 개의 합과 마지막으로 탐색한 물건의 무게의 합이 C를 만족한다면 1을 출력하고 아니라면 탐색 범위를 바꾸게 되는 원리이다.

물건 탐색

Arrays.sort(weight);

// 최대 물건 3개
for(int i=0;i<N;i++){

    // C에 맞는 경우
    if(weight[i]==C){
        System.out.println(1);
        System.exit(0);
    }
    for(int j=i+1;j<N;j++){
        // C에 맞는 경우
        if(weight[i]+weight[j]==C){
            System.out.println(1);
            System.exit(0);
        }

        // 나머지 하나 탐색
        int left=0;
        int right=N-1;
        while(left<=right){
            int mid=(left+right)/2;

            if(weight[i]+weight[j]+weight[mid]==C){
                if(mid!=i && mid!=j) {
                    System.out.println(1);
                    System.exit(0);
                }
            }

            if(weight[i]+weight[j]+weight[mid]>C){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
    }

}

이분탐색을 진행하기 위해서는 우선 정렬이 필요하다.

Arrays.sort(weight);

물건의 무게 정보가 들어간 배열을 정렬해주고 시작한다.

이중 for문을 이용하여 처음의 물건 두 개를 선택한다.

우선 첫번째 반복문에서 물건을 선택하면 무게 C와 같은지 확인한다.

같다면 1을 출력하고 프로그램을 종료시키고, 아니라면 중첩된 for문으로 들어가 물건 하나를 더 고른다.

for(int i=0;i<N;i++){

    // C에 맞는 경우
    if(weight[i]==C){
        System.out.println(1);
        System.exit(0);
    }
...
}

두 물건의 무게의 합이 C인지 확인하고 위와 같은 과정을 한 번 더 수행한다.

C 무게가 아니라면 또 한번 더 물건을 탐색하게 되는데, 이때 이분탐색을 이용한다.

int left=0;
int right=N-1;
while(left<=right){
    int mid=(left+right)/2;

    if(weight[i]+weight[j]+weight[mid]==C){
        if(mid!=i && mid!=j) {
            System.out.println(1);
            System.exit(0);
        }
    }

    if(weight[i]+weight[j]+weight[mid]>C){
        right=mid-1;
    }
    else{
        left=mid+1;
    }
}