[백준 Java] 19942번 다이어트

안나·2024년 2월 8일
알고리즘 문제풀이
0

Algorithm-Problem-Solving

목록 보기
20/23
post-thumbnail

💡문제

[Gold IV] 다이어트 - 19942

문제 링크

성능 요약

메모리: 15052 KB, 시간: 104 ms

🤔접근법

N개의 식자재 중에 단백질, 지방, 탄수화물, 비타민의 최소 기준을 만족하고 최소 비용을 가지도록 식자재를 선택하는 문제

범위 체크 및 시간복잡도 예상

  • 2 ≤ N < 15
  • 0≤ 최소 영양소 기준 ≤ 500
  • 최소 영양소들의 합 > 0
  • 0 ≤ 식자재의 영양소와 비용 ≤ 500

풀이법

⭕ 접근 방법. 조합, 부분집합

  1. 식재료들로 조합할 수 있는 모든 조합을 만든다.
  2. 만든 조합이 최소 조합인지 확인한다.
  3. 최저 영양소 기준을 만족하는지 확인한다.
  4. 뽑은 식재료들의 번호들의 문자열이 사전순인지 확인한다.
  5. 모든 조건에 만족한다면 최소 비용과 결과를 저장한다.

그렇다면 식재료들로 조합할 수 있는 모든 조합은 어떻게 만들까 ?

재귀 함수를 이용하자.

각 식재료들은 선택할 지, 선택하지 않을 지로 나뉜다.

A 식재료를 선택한 경우 다음 B 식재료를 보고 또 선택할지 선택하지 않을지 고른다.

만약 A 식재료를 선택하지 않은 경우도 다음 B 식재료를 보고 선택할지 선택하지 않을지 고른다.

다음 C 식재료도 , D 식재료도 마찬가지 이다.

여기서 중요한 건 고른 식재료들의 영양소합과 비용합이다.
식재료를 골랐는지 고르지 않았는지에 따라 값이 달라지기 때문에 이때는 재귀함수의 파라미터로 저장하여 상태에 따른 값을 가지고 가면 된다.

private static void powerset(int foodIdx, int totalCost, int[] total) {

        // foodIdx번째 식재료 선택
        selectedFood.add(foodIdx);
        for (int i = 0; i < 4; i++) {
            total[i] += foodInfo[foodIdx][i]; // 선택된 식재료의 영양소 합 구하기
        }
        powerset(foodIdx + 1, totalCost + foodInfo[foodIdx][4], total); // 현재 식재료 선택하고 다음 식재료로 넘어감

        // foodIdx번째 식재료 선택 안 함
        selectedFood.remove(selectedFood.size() - 1); // 마지막으로 선택된 식재료 제거
        for (int i = 0; i < 4; i++) {
            total[i] -= foodInfo[foodIdx][i]; // 선택된 식재료의 영양소 합 갱신 (선택하지 않는 경우)
        }
        powerset(foodIdx + 1, totalCost, total); // 현재 식재료를 선택하지 않고 다음 식재료로 넘어감

}

그렇게 쭉쭉 재귀를 타고 들어가다가 마침내 모든 식재료를 선택할지, 선택하지 않을지 다 결정을 한다면

3가지 조건을 만족하는지 판단하면 된다.

그러나 이때 4가지 식재료 중에 2가지만 골랐음에도 최소 비용보다 비용이 더 높아지는 경우가 있다.

이런 경우 계속해서 뒤에 식재료를 고르는 걸 고려할 필요가 없다. 이미 비용이 높아졌으니 최종 비용은 같거나 더 크기 때문이다. 그래서 중간에 가지 치기를 한다.

private static void powerset(int foodIdx, int totalCost, int[] total) {
        if (totalCost > minCost) return; // 조건 1. 현재 비용이 최소 비용보다 크면 중단

        if (foodIdx > N) { // 모든 식재료를 고려했을 때
            for (int i = 0; i < 4; i++) {
                if (min[i] > total[i]) return; // 조건 2. 최소 영양소를 만족하지 못하면 중단
            }

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < selectedFood.size(); i++) {
                sb.append(selectedFood.get(i) + " "); // 선택된 식재료 번호 저장
            }

            if (totalCost == minCost) { // 현재 비용이 최소 비용과 같을 때
                // result의 아스키코드 - sb의 아스키코드 => 음수이면 sb가 더 크다는 뜻이니까 사전순으로 뒤여야함.
                if (result != null && result.compareTo(sb.toString()) < 0) return; // 조건 3. 사전순으로 더 빠른 결과가 이미 저장되어 있으면 중단
            }

            minCost = totalCost; // 최소 비용 갱신
            result = sb.toString(); // 결과 저장
            return;
        }

        // foodIdx번째 식재료 선택
        selectedFood.add(foodIdx);
        for (int i = 0; i < 4; i++) {
            total[i] += foodInfo[foodIdx][i]; // 선택된 식재료의 영양소 합 구하기
        }
        powerset(foodIdx + 1, totalCost + foodInfo[foodIdx][4], total); // 현재 식재료 선택하고 다음 식재료로 넘어감

        // foodIdx번째 식재료 선택 안 함
        selectedFood.remove(selectedFood.size() - 1); // 마지막으로 선택된 식재료 제거
        for (int i = 0; i < 4; i++) {
            total[i] -= foodInfo[foodIdx][i]; // 선택된 식재료의 영양소 합 갱신 (선택하지 않는 경우)
        }
        powerset(foodIdx + 1, totalCost, total); // 현재 식재료를 선택하지 않고 다음 식재료로 넘어감
}

각 식재료에 따라서 선택함, 선택하지 않음 두가지 선택권이 있으므로 2N2^N

➡️ 해당 풀이법의 시간 복잡도 : O(2N)O(2^N)




문자열.compareTo(문자열)

  • 사전적 방식으로 문자열 간의 차이를 계산
  • 비교 대상 문자열의 각 문자들을 첫번째 자리부터 하나씩 비교하다가 서로 다른 문자들을 만나면 아스키 코드 값의 차이를 반환하고 비교를 마친다.
  • “334”.compareTo”234”
  • “756”.compareTo”719”
  • “2539”.compareTo”856”

😎SUCCESS

담박에 성공하지 못한 이유는 ?

  • 최저 영양소 기준을 만족하는 조합이 없는 경우 -1을 출력하라는 조건을 누락함
  • 최소 비용이 같은 경우가 여러 경우라면 사전순으로 우선인 것을 출력하라는 것을 누락함

결론 : 문제를 잘 읽자 ㅎ!

👩‍💻 코드

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

public class Main_19942 {
    static int N; // 식재료 개수
    static int min[]; // 최소로 얻어야 하는 영양소
    static int foodInfo[][]; // 각 식재료의 영양 정보와 가격
    static int minCost = Integer.MAX_VALUE; // 최소 비용
    static ArrayList<Integer> selectedFood; // 선택된 식재료의 번호를 저장하는 리스트
    static String result; // 최종 결과를 저장하는 문자열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 식재료 개수 입력
        min = new int[4]; // 최소 영양소 배열 초기화
        StringTokenizer st = new StringTokenizer(br.readLine()); // 최소 영양소 입력 받기
        for (int i = 0; i < 4; i++) {
            min[i] = Integer.parseInt(st.nextToken());
        }

        foodInfo = new int[N + 1][5]; // 각 식재료의 정보를 담는 배열 초기화
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine()); // 식재료 정보 입력 받기
            for (int j = 0; j < 5; j++) {
                foodInfo[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int total[] = new int[4]; // 선택된 식재료의 영양소 합을 저장하는 배열 초기화
        selectedFood = new ArrayList<>(); // 선택된 식재료의 번호를 저장할 리스트 초기화
        powerset(1, 0, total); // 조합 생성 및 검사 함수 호출

        // 결과 출력
        if (result == null) {
            System.out.println(-1); // 조건을 만족하는 식재료가 없는 경우 -1 출력
        } else {
            System.out.println(minCost); // 최소 비용 출력
            System.out.println(result); // 선택된 식재료 번호 출력
        }
    }

    // powerset 함수: 조합 생성 및 검사
    private static void powerset(int foodIdx, int totalCost, int[] total) {
        if (totalCost > minCost) return; // 현재 비용이 최소 비용보다 크면 중단

        if (foodIdx > N) { // 모든 식재료를 고려했을 때
            for (int i = 0; i < 4; i++) {
                if (min[i] > total[i]) return; // 최소 영양소를 만족하지 못하면 중단
            }

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < selectedFood.size(); i++) {
                sb.append(selectedFood.get(i) + " "); // 선택된 식재료 번호 저장
            }

            if (totalCost == minCost) { // 현재 비용이 최소 비용과 같을 때
                // result의 아스키코드 - sb의 아스키코드 => 음수이면 sb가 더 크다는 뜻이니까 사전순으로 뒤여야함.
                if (result != null && result.compareTo(sb.toString()) < 0) return; // 사전순으로 더 빠른 결과가 이미 저장되어 있으면 중단
            }

            minCost = totalCost; // 최소 비용 갱신
            result = sb.toString(); // 결과 저장
            return;
        }

        // foodIdx번째 식재료 선택
        selectedFood.add(foodIdx);
        for (int i = 0; i < 4; i++) {
            total[i] += foodInfo[foodIdx][i]; // 선택된 식재료의 영양소 합 구하기
        }
        powerset(foodIdx + 1, totalCost + foodInfo[foodIdx][4], total); // 현재 식재료 선택하고 다음 식재료로 넘어감

        // foodIdx번째 식재료 선택 안 함
        selectedFood.remove(selectedFood.size() - 1); // 마지막으로 선택된 식재료 제거
        for (int i = 0; i < 4; i++) {
            total[i] -= foodInfo[foodIdx][i]; // 선택된 식재료의 영양소 합 갱신 (선택하지 않는 경우)
        }
        powerset(foodIdx + 1, totalCost, total); // 현재 식재료를 선택하지 않고 다음 식재료로 넘어감
    }
}
profile
안나
이전 포스트

[백준 Java] 1637번 날카로운 눈

다음 포스트

[백준 Java] 2580번 스도쿠

0개의 댓글