[코드트리 챌린지] 5주차 DP l - 아이템을 적절히 고르는 문제 / 부분 수열의 합이 m

저번 진단때는 운좋게 푼 문제가 있었다보니 점수가 떨어졌다. 사실 이게 맞는 점수 인 듯

https://www.codetree.ai/missions/2/problems/the-sum-of-the-subsequences-is-m/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[105];
int dp[10005];
// dp[i] : i 값을 만들기 위해 필요한 최소 길이의 부분수열

void Initialize() {
    dp[0] = 0;

    for (int i = 1; i <= m; i++) {
        dp[i] = 10000000;
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    Initialize();


    for (int i = 0; i < n; i++) {
        for (int j = m; j >= 0; j--) {
            // j에 대한 for문을 거꾸로 진행시켜
            // 수열 내 값이 중복으로 사용됨을 막는다.
            // 이전 dp 풀이와는 다르게 수열 값을 도는 부분이
            // 바깥 for문에 존재하는데 이는 수열 내 값 중복 사용을 막기 위해서이다.
            if (j >= arr[i]) {
                dp[j] = min(dp[j], dp[j - arr[i]] + 1);
            }
        }
    }

    if (dp[m] == 10000000) {
        cout << -1;
    }
    else {
        cout << dp[m];
    }
}

n,m을 입력받아 주어진 수열을 배열 arr에 입력받습니다.

Initialize() 함수를 통해 dp[i]를 초기화해줍니다. 우리가 구해야할 것은 수열의 최소 길이이므로
dp 배열을 모두 큰 값으로 초기화해줍니다.

dp 배열을 채우는 부분이 이전 dp 문제를 풀때와 달라진 부분이 존재합니다.
이전 dp문제에서는 수열 값을 중복해서 사용이 가능했으므로 수열 값을 도는 for문을 안쪽에 위치시켰는데
이번 문제에서는 수열 값을 중복으로 사용할 수 없으므로 for문을 바깥 쪽으로 위치시키도록 했습니다.

(ex) dp[12]의 경우 수열 값을 도는 for문이 바깥쪽에 존재한다면 dp[12 - 6] + 1 과 같이 6이 두번
중복되어 사용되는 경우가 발생합니다.)

또한, 안쪽 for문을 0부터가 아닌 m부터 시작해 감소하게 설정을 했는데 이 또한 수열 값의 중복사용을
예방합니다.

(ex) dp[4]의 경우 for문이 0부터 시작하게 된다면 dp[4 - 2]인 dp[2]값이 이미 채워져있어 2가 중복사용
되는 경우가 발생합니다.)

위 두가지 경우를 고려해 for문을 설정한 뒤 dp 배열을 채워주도록 합니다.

이번 문제의 경우 풀이법을 떠올리지 못해 풀이를 참고하였습니다.

난이도가 점점 올라가다 보니 이제부터는 간단히 문제를 풀 수 없을 것 같습니다.