[BOJ 13910] 개업 - java

백준 13910번: 개업

풀이

동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다

👉 짜장면 i개를 만들기 위한 횟수를 구하기 위해, a + b = i 조합을 활용한다!

1. a, b 크기의 wok이 존재하여, 한 번에 조리가 가능한가?

   • if (a == b && wok[a] ≥ 2) : a와 b의 크기가 같은 경우 a 크기의 wok이 2개 이상 존재하는지 체크
   • if (a ≠ b && wok[a] > 0 && wok[b] > 0) : a와 b의 크기가 다른 경우 각각의 wok이 존재하는지 체크

2. 만약 한 번에 조리가 불가능하다면,

   dp[i] = Math.min(dp[i], dp[a] + dp[b])

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= i / 2; j++) {
        if (j == i - j && wok[j] >= 2) dp[i] = 1;
        else if (j != i - j && wok[j] > 0 && wok[i - j] > 0) dp[i] = 1;
        else if (dp[j] != MAX && dp[i - j] != MAX) {
            dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
        }
    }
}

전체 코드

public class BOJ_13910 {

    static final int MAX = 10001;

    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 m = Integer.parseInt(st.nextToken()); // 웍의 개수

        int[] wok = new int[MAX];
        wok[0] = 1;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            wok[Integer.parseInt(st.nextToken())]++;
        }

        int[] dp = new int[n + 1];
        Arrays.fill(dp, MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i / 2; j++) {
                if (j == i - j && wok[j] >= 2) dp[i] = 1;
                else if (j != i - j && wok[j] > 0 && wok[i - j] > 0) dp[i] = 1;
                else if (dp[j] != MAX && dp[i - j] != MAX) {
                    dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
                }
            }
        }
        System.out.println(dp[n] == MAX ? -1 : dp[n]);
    }
}