[백준/C++]#13910, 13902- 개업, 개업2

코드

#include <bits/stdc++.h>

using namespace std;

// 웍 넣는 배열
int arr[101];
// Dp 저장 배열
int D[20001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    for (int i=0; i<M; i++) cin >> arr[i];
    // Dp 최댓값으로 초기화
    fill(D, D+20001, INT_MAX);
    // 한번의 요리에 해당하는 DP 채움 (1개의 웍 크기, 2개의 웍 크기)
    for (int i=0; i<M; i++) {
        for (int j=0; j<M; j++) {
            if (i == j) D[arr[i]] = 1;
            else D[arr[i]+arr[j]] = 1;
    }
    // N번까지 가능한 요리의 횟수 최솟갑 DP에 저장
    for (int i=1; i<=N; i++) {
        // 채워진 DP는 패스
        if (D[i] == 1) continue;
        // 5 = 4 + 1, 3 + 2  또는    6 = 3 + 3, 4 + 2, 5 + 1  해당하는 수만큼 반복
        for (int j=1; j<=i/2; j++) {
            // valid하지 않은 DP는 참조하지 못함
            if (D[i-j] == -1 || D[j] == -1) continue;
            D[i] = min(D[i], D[i-j] + D[j]);
        }
        // 변화 없으면 valid하지 않음
        if (D[i] == INT_MAX) D[i] = -1;
    }
    cout << D[N] << '\n';
    return 0;
}

풀이

D[x] = x만큼 짜장면 요리하는데 드는 최소 횟수

 

1. 한손 또는 두손으로 가능한 "한번의 요리"를 DP 테이블에 작성한다.
2. DP[N]까지 반복문을 돌며, min(현재 DP값, 그릇수가 일치하는 이전 DP들의 합)을 DP 테이블에 넣는다. 

예시는 다음과 같다.

D[5] = min(D[5], D[1] +D[4]) = D[1] +D[4]

- 계산을 줄이기 위해, 반복문의 조건을 i/2보다 작거나 같을 때로 했으며 valid하지 않은 경우 continue를 사용했다.

---

 

+a

• D 배열은 최대 20000개까지 존재가능하다, 웍의 최대 크기가 N이므로 2N = 20000 
• DP로 진행, 그리디도 가능할거같음..

 

- 개업2의 경우 웍의 개수인 arr 배열의 크기를 1001로 바꿔주면 통과한다.

 

- 웍의 크기가 동일한 경우에도 "한번의 요리"를 DP 테이블에 저장하고 나면, 동일한 알고리즘으로 해결된다.