[BOJ/Java] 19942. 다이어트

[BOJ/Java] 19942. 다이어트

19942번: 다이어트

---

문제 해석

다이어트 문제(BOJ 19942)는 주어진 영양소의 최소 요구량을 만족하는 식단을 찾는 문제이다. 각 식단은 단백질, 지방, 탄수화물, 비타민을 포함하며, 주어진 요구량을 만족하는 식단 중 최소 비용을 갖는 식단을 찾는 것이 목표이다.

풀이 과정

이 문제는 부분 집합의 속성을 활용하여 모든 가능한 조합을 탐색하는 방법으로 해결할 수 있다. 재귀적 방법으로 각 음식을 선택하거나 선택하지 않는 모든 경우를 고려하며, 최소 비용을 업데이트하는 방식을 사용한다. 각 음식을 선택할 때마다 현재의 영양소 합계에 해당 음식의 영양소를 추가하고, 선택하지 않을 경우에는 제외한다. 만약 현재까지의 선택이 요구 영양소를 만족하고, 이때의 총 비용이 현재까지의 최소 비용보다 작다면, 최소 비용과 선택된 식단을 업데이트한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No19942;

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static int N; // 음식의 수
    private static Food LIMIT; // 필요 영양소 최소량
    private static Food[] foods; // 각 음식의 영양소 및 비용 정보
    private static int minCost = Integer.MAX_VALUE; // 최소 비용 초기화
    private static String ans; // 최소 비용을 만족하는 식단 문자열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine()); // 음식의 수 입력 받기

        StringTokenizer st = new StringTokenizer(br.readLine());
        LIMIT = new Food(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 필요 영양소 정보 입력 받기

        foods = new Food[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            foods[i] = new Food(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 각 음식의 정보 입력 받기
        }

        recursive(0, new Food(0, 0, 0, 0, 0), new StringBuilder()); // 재귀 함수 호출

        if (minCost == Integer.MAX_VALUE) sb.append(-1); // 만족하는 식단이 없는 경우 -1 출력
        else sb.append(minCost).append("\n").append(ans); // 최소 비용 및 식단 출력

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void recursive(int i, Food sum, StringBuilder sb) {
        if (sum.check() && sum.c < minCost) {
            ans = sb.toString(); // 식단 문자열 업데이트
            minCost = sum.c; // 최소 비용 업데이트
        }

        if (i == N) return; // 모든 음식을 고려했을 경우 종료

        sum.add(foods[i]); // 현재 음식을 선택
        recursive(i+1, sum, sb.append(i+1).append(" ")); // 선택된 음식을 문자열에 추가

        sum.remove(foods[i]); // 선택한 음식 제거
        recursive(i+1, sum, sb.delete(sb.length() - ((i+1) < 10 ? 2 : 3), sb.length())); // 제거된 음식 문자열에서 삭제
    }

    static class Food {
        int p, f, s, v, c; // 영양소 및 비용

        public Food(int p, int f, int s, int v, int c) {
            this.p = p;
            this.f = f;
            this.s = s;
            this.v = v;
            this.c = c;
        }

        public Food(int p, int f, int s, int v) {
            this.p = p;
            this.f = f;
            this.s = s;
            this.v = v;
        }

        public void add(Food f) {
            this.p += f.p;
            this.f += f.f;
            this.s += f.s;
            this.v += f.v;
            this.c += f.c;
        }

        public void remove(Food f) {
            this.p -= f.p;
            this.f -= f.f;
            this.s -= f.s;
            this.v -= f.v;
            this.c -= f.c;
        }

        public boolean check() { // 영양소 요구량 만족 확인
            return this.p >= LIMIT.p && this.f >= LIMIT.f && this.s >= LIMIT.s && this.v >= LIMIT.v;
        }
    }
}

시간 복잡도 분석

이 문제의 시간 복잡도는 모든 음식에 대해 선택하는 경우와 선택하지 않는 경우의 조합을 모두 탐색하기 때문에 𝑂(2^𝑁)이다.

느낀점

재귀와 백트래킹을 사용하여 문제를 해결하는 과정에서 문제의 복잡도를 높이지 않고 효율적으로 모든 경우를 탐색할 수 있는 방법을 배웠다. 코드의 각 부분에서 주석을 추가하여 더 이해하기 쉽게 만들었고, 최적화를 위해 조건을 명확히 하는 방법을 배울 수 있었다.