[백준] 18114번 - 블랙 프라이데이 by Java(자바)

✨ 문제

✨ 풀이

✔️ 선택할 수 있는 물건의 개수는 1~3개이며, 만약 그 물건들의 무게 합들 중 어떠한 것도 C와 같지 않으면 0을 출력한다. 만약 C와 같은 값이 나오면 1을 출력한다.

📍 주의할 점

✔️ 같은 물건을 중복 선택하는 것은 불가능하다.
✔️ 판매하는 물건들의 무게는 모두 다르다.
✔️ 선택할 수 있는 물건은 최대 3개이다.

📍 입력

✔️ 첫 번째 줄: 물건의 개수 N개, 제시하는 무게 C
👉🏻 N, C는 공백으로 구분되어 주어진다. 따라서, BufferedReader 클래스 사용해서 N C를 입력받고 StringTokenizer 클래스를 이용해서 N, C를 토큰으로 분리해 각 변수에 저장한다.

✔️ 두 번째 줄: N개의 물건 각각의 무게 w
👉🏻 N개의 w 또한 공백으로 구분되어 주어진다. 따라서 먼저 한 줄 입력을 받고 for 반복문을 사용해 총 N번의 반복 동안 각 물건의 무게를 nextToken()을 사용해 분리하고 ArrayList<>로 생성해놓은 w 리스트에 .add() 메서드로 각 무게를 배열에 추가한다. 이때, 선택하는 물건의 개수가 1개인 경우를 같이 고려하도록 한다. (선택하는 물건의 개수가 1개인 경우의 풀이는 바로 다음에 있다!)

📍 선택하는 물건의 개수 - 1개

✔️ 주어진 N개의 물건의 무게 중 C와 같은 값이 존재하는지를 확인한다.
👉🏻 입력을 받은 후 다시 for 반복문을 사용해 w 리스트에서 각 값을 꺼내 C와 비교해도 되지만, 입력을 받고 토큰으로 분리해 리스트에 저장할 때 고려하도록 코드를 작성했다. 첫 번째 토큰을 분리하고 w 리스트에 넣고 그 다음 줄에서 해당 리스트의 인덱스 0에 위치하는 첫 번째 원소의 값을 .get(0)으로 가져와 C와 같은지 비교한다.

🔻 이 부분의 코드는 다음과 같다.

st = new StringTokenizer(br.readLine());
ArrayList<Integer> w = new ArrayList<>();
for(int i = 0; i < N; i++) {
	w.add(Integer.parseInt(st.nextToken()));
	// 1개 선택
	if(w.get(i) == C) {
		System.out.println(1);
		return;		// 만약 w.get(i)가 C와 같으면 물건을 2개, 3개 선택해서 나오는 경우를 고려하지 않아도 되므로 return을 작성한다.
	}
}

📍 선택하는 물건의 개수 - 2, 3개

✔️ 배열을 "정렬"하고 선택하는 물건의 수가 2개 3개인 경우를 하나의 for 반복문 안에서 고려한다.

✔️ 제일 큰 수와 제일 작은 수로 시작하여 물건 선택의 폭을 줄인다.
👉🏻 배열을 오름차순으로 정렬하고 제일 작은 첫 번째 원소와 제일 큰 마지막 원소를 시작으로 해서 그 둘의 합(weigth)이 C보다 큰지 작은지에 따라 경우를 분리하여 물건의 개수가 2개인 경우를 고려했다
👉🏻 만약 두 물건의 합이 C보다 크면 제일 큰 마지막 원소 바로 앞에 있는 두 번째로 큰 원소로 이동하여 첫 번째 원소와의 합을 구하여 다시 C와 비교하도록 했다. 만약 C보다 작으면 제일 작은 원소가 아니라 두 번째로 작은 원소로 이동하여 제일 큰 원소와의 합을 구해 C와 다시 값을 비교한다.

✔️ 우리의 목표는 물건들의 무게 합이 C와 같은지 확인하는 것임을 잊지 말자!
👉🏻 물건을 3개 고르는 경우는 반복문 2, 3번을 작성하지 않고 여기서 약간의 응용만 하면 된다. 물건을 2개 골라놓은 상태에서는 물건 3개를 고르기 위해 다시 인덱스 3개를 활용할 필요가 없다. 우리는 물건들의 합이 C가 될 수 있는지만 확인하면 되므로 C에서 구해놓은 물건 2개의 합을 뺀 수가 리스트에 있는지만 확인하면 된다. 이때 .indexOf() 메서드를 사용하면 편리하다. 단, 물건의 중복 선택은 불가능하기 때문에 w.indexOf(C-weight)의 값이 i와 j가 되어서는 안 된다.

🔻 이 부분의 코드는 다음과 같다.

// 2개, 3개 선택
Collections.sort(w);
int i = 0, j = N-1, weight;
while(i < j) {
    weight = w.get(i) + w.get(j);
    if(weight > C) {
        j--;
    }
    else if(weight == C) {
        System.out.println(1);
        return;
    }
    else {
        if(w.indexOf(C-weight) < j && w.indexOf(C-weight) > i){
            System.out.println(1);
            return;
        }
        i++;
    }
}

📍 무게의 합이 C가 나오지 않는 경우

✔️ 선택할 수 있는 물건의 개수는 1~3개이고, 이 물건들의 합이 모두 C가 되지 않는다면 0을 출력한다.

📍 예시로 이해하는 풀이

문제를 풀다 생각한 예시를 적어놓으려고 한다! 개인적으로 예시를 보며 풀이를 이해하는 것이 더 쉽다고 생각한다,,
✔️ 입력

6 9
1 2 3 4 10 14

✔️ 우리는 물건 1~3개를 선택해서 그 물건들의 합이 9가 되는지 확인하고 가능하면 1을, 아니면 0을 출력한다.

✔️ 출력(답)

1
👉🏻 이유 : 서로 다른 물건 3개의 합 2 + 3 + 4 = 9 이기 때문이다.

✔️ 과정 설명
👉🏻 w 리스트에 무게 1, 2, 3, 4, 10, 14가 저장되고 각 무게가 9와 같은지 비교한다. 하지만 물건 1개를 선택해서 그 물건의 무게가 9가 되는 경우는 존재하지 않는다.
👉🏻 이제 물건 2개와 3개를 골랐을 때를 고려한다. 그 전에 먼저 리스트를 오름차순으로 정렬한다. (1 2 3 4 10 14)
👉🏻 리스트의 제일 작은 값과 큰 값인 1과 14를 시작으로 한다. 두 물건의 합은 15이므로 C인 9보다 크므로 제일 큰 14를 버리고 그 다음으로 큰 10을 선택한다. 1과 10의 합은 11이므로 또 9보다 크므로 10을 버리고 그 다음으로 큰 4를 선택한다. 이제 1과 4의 합은 5로 9보다 작으므로 이제 물건 3개를 선택하는 것을 함께 고려한다. 9에서 5를 뺀 4를 찾아보지만 무게 4를 가진 물건을 하나밖에 존재하지 않고 이미 물건 2개를 고를 때 골라진 물건에 속하므로 다음 과정으로 넘어간다. 그래도 1과 4의 합인 5가 9보다 작으므로 1보다 큰 2를 선택한다. 이제 2와 4의 합은 6이고 9에서 6을 뺀 3이 있나 확인한 결과, 2 3 4는 서로 다른 물건의 무게이고 합하면 9가 되므로 1을 출력하고 프로그램을 종료한다.

✨ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

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());		// 물건의 개수
        int C = Integer.parseInt(st.nextToken());		// 무게
        
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> w = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            w.add(Integer.parseInt(st.nextToken()));
            // 1개 선택
            if(w.get(i) == C) {
                System.out.println(1);
                return;
            }
        }
        // 2개, 3개 선택
        Collections.sort(w);
        int i = 0, j = N-1, weight;
        while(i < j) {
            weight = w.get(i) + w.get(j);
            if(weight > C) {
                j--;
            }
            else if(weight == C) {
                System.out.println(1);
                return;
            }
            else {
                if(w.indexOf(C-weight) < j && w.indexOf(C-weight) > i){
                    System.out.println(1);
                    return;
                }
                i++;
            }
        }
        System.out.println(0);
    }	
}

✨ 결과

👉🏻 풀고 나서 다른 코드도 확인했는데 자바로 푼 사람이 많지 않고 정답 코드가 많은 편은 아니라서 다음 학기에 C++ 배운 후에 다시 풀어보고 확인해봐야겠다!!

✨ 느낀점

문제 처음 봤을 때 선택할 수 있는 물건의 최대 개수 3개를 문제 읽는데 놓치고 4개 5개 ... N-1개는 어떻게 구하나 생각한 다음에 20분 후에 다시 문제 읽는데 3개라고 적혀져 있어서 다시 1개 2개 3개 순서로 차근차근 풀기 시작했다. 원래 처음에는 선택하는 물건이 2개 3개인 경우를 나눠서 작성했는데 시간 초과가 나와서 소스 코드를 확인해봤다. 그랬더니 2개 3개 케이스는 쉽게 합쳐서 한 번의 반복문 안에 같이 작성할 수 있어 합쳤다. 일단 어떻게 풀지는 쉽게 나왔는데 시간 초과가 나오거나 몇몇 경우를 생각하지 않아서 다시 고치느라 시간이 걸렸다. 그래도 배울 수 있는 점이 되게 많은 문제였다고 생각한다. 이제 매주 이 문제랑 비슷한 난이도의 문제를 골라서 풀어봐야겠다.