문제

학생수와 예산의 수가 주어지고,
학생 수 만큼 각각 물건 값과 배송비가 주어진다.
물건 값을 반으로 할인받을 수 있는 할인쿠폰이 존재할때
최대로 선물할 수 있는 학생의 수는 ?

입력 예시

4 2
1 3
2 3
2 2
0 1

틀린 답변

import java.util.*;

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

        int n = sc.nextInt();
        int money = sc.nextInt();

        int[][] lst = new int[n][3];

        for (int i = 0; i < n; i++) {
            lst[i][0] = sc.nextInt() / 2; // 가격
            lst[i][1] = sc.nextInt(); // 추가 비용
            lst[i][2] = lst[i][0] + lst[i][1]; // 총 비용
        }

        Arrays.sort(lst, (a, b) -> {
            if (a[2] != b[2]) {
                return Integer.compare(a[2], b[2]); // 총 비용 기준 오름차순
            } else {
                return Integer.compare(b[0], a[0]); // 가격 기준 내림차순
            }
        });

        boolean usedDiscount = false; // 할인 사용 여부
        int sum = 0; // 현재 총 비용
        int count = 0; // 구매 가능한 아이템 개수

        for (int i = 0; i < n; i++) {
            int price = lst[i][0];
            int additionalCost = lst[i][1];
            int totalCost = price * 2 + additionalCost;

            if (!usedDiscount && sum + price + additionalCost <= money) {
                // 할인 적용 가능한 경우
                sum += (price / 2) + additionalCost;
                usedDiscount = true;
                count++;
            } else if (sum + totalCost <= money) {
                // 할인 없이 구매 가능한 경우
                sum += totalCost;
                count++;
            } else {
                // 더 이상 구매 불가
                break;
            }
        }

        System.out.println(count);
    }
}

틀린 이유 생각해보기

• 정렬을 애매하게 함 -> 여러버전으로 하긴 했지만
  (할인 받은 금액 기준, 할인 안받은 금액 기준, 총액 기준)
  총액을 기준으로 했을 때 할인 했을 때의 정렬이 애매했다고 생각
• 구한 값이 최대가 아닐 확률이 큼
  => 최소 금액부터 더했을 때, 예산을 다 쓰지 않고 끝날 수 있음
  (다른 순서의 상품을 할인 받았을 경우에 더 많이 살 수 있는 경우가 존재)
• 결론적으로 완전 탐색이 아님.

왜 완전탐색이 아니였을까?

• 정렬 기반 최적화:
  아이템들을 정렬하여 "할인된 비용 + 추가 비용" 또는 "총 비용" 기준으로 우선순위를 조정했습니다.
  정렬을 통해 탐색 공간을 줄이고, 더 유리한 아이템을 먼저 선택하도록 했습니다.
• 조건 기반 탐색:
  할인 조건이 적용된 아이템을 우선적으로 고려하거나, 예산 초과 시 바로 중단하는 로직으로 탐색 범위를 제한했습니다.

완전 탐색과의 차이점

• 완전 탐색:
  모든 아이템 조합(즉, 각 아이템에 대해 할인 여부를 결정한 모든 가능한 경우의 수)을 탐색합니다.
  시간 복잡도는 일반적으로 매우 높으며,
  2^n 혹은 n!처럼 입력 크기에 따라 급격히 증가합니다.
• 당신의 코드:
  정렬과 조건을 통해 탐색 범위를 줄이고, 특정 상황에서 최적의 결과를 빠르게 찾으려는 "탐욕 알고리즘"에 가깝습니다.
  예산 내에서 최대 아이템을 구매할 수 있는 상황을 빠르게 계산하기 위해 일부 경우를 제외하거나 중단합니다.

정답 코드

import java.util.*;

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

        int n = sc.nextInt();
        int money = sc.nextInt();

        int[][] lst = new int[n][3];

        for (int i = 0; i < n; i++) {
            lst[i][0] = sc.nextInt(); // 원래 가격
            lst[i][1] = sc.nextInt(); // 추가 비용
            lst[i][2] = lst[i][0] + lst[i][1]; // 총 비용
        }

        // 총 비용 기준 오름차순 정렬
        Arrays.sort(lst, (a, b) -> Integer.compare(a[2], b[2]));

        int maxCount = 0;

        // 모든 아이템에 대해 한 번씩 할인 적용
        for (int i = 0; i < n; i++) {
            int remainingMoney = money - (lst[i][0] / 2 + lst[i][1]); // i번 아이템 할인 적용
            if (remainingMoney < 0) continue; // 할인 적용해도 예산 초과 시 건너뜀

            int count = 1; // 할인 적용한 아이템 포함
            for (int j = 0; j < n; j++) {
                if (i == j) continue; // 할인 적용한 아이템은 제외
                if (remainingMoney >= lst[j][2]) {
                    remainingMoney -= lst[j][2];
                    count++;
                } else {
                    break;
                }
            }
            maxCount = Math.max(maxCount, count); // 최대 구매 가능 개수 갱신
        }

        System.out.println(maxCount);
    }
}

완전탐색으로 해결..

https://www.codetree.ai/trails/complete/curated-cards/test-the-grace-form-teacher-3/description