코테 문제풀이 6일차

👑문제: [프로그래머스 Level2]

BOJ 13910 개업

풀이 시 고려해야 할 점

손이 두개라는 사실이 매우 중요했다!!
처음에는 그릇의 개수에 상관없이 한번에 모두 조리가 가능한 것이라는 생각에 도대체 어떻게 풀어야 할지 감이 안잡혔는데, 두개정도면 미리 합을 구한 뒤에 dp를 돌리면 되서 매우 간편해졌다.
하지만 주의해야 할 점은 합을 구해서 리스트에 넣을 때 주문받은 짜장면의 그릇 수를 넘기면 BOF가 발생을 하므로 꼭 그릇 수보다 작은 것만 넣어야 한다.

풀이 과정

package BOJ.DP;

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

public class G13910 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        int[] S = new int[M];
        int[] dp = new int[N+1];
        for (int i = 0; i < N+1; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            S[i] = Integer.parseInt(st.nextToken());
            arr.add(S[i]);
            dp[S[i]] = 1;
        }
        dp[0] = 0;
        for (int i = 0; i < M-1; i++) {
            for (int j = i+1; j < M; j++) {
                if(S[i]+S[j]<=N) {
                    arr.add(S[i]+S[j]);
                    dp[S[i]+S[j]] = 1;
                }
            }
        }

        Iterator<Integer> it = arr.iterator();
        while(it.hasNext()) {
            int n = it.next();
            for (int i = n; i < N+1; i++) {
                if(dp[i-n] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - n] + 1);
                }
            }
        }
        if(dp[N] == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(dp[N]);
    }
}

느낀점

간단한 문제인데..왜이렇게 틀렸는지ㅠㅜㅜ
처음에 설계를 잘 한뒤에 문제를 풀어보자!!