Baekjoon 7579: 앱

문제 설명

• 문제 링크
• Algorithm: DP, Knapsack

 

• 난이도: Gold 3 ('24. 9. 11.)
• 출처: solved.ac class5+
• 요약: 적절히 $i$개의 앱을 비활성화해서 $M$ 바이트 이상을 확보하되 $c$를 최소화

풀이

접근1

• 조건 1: $(n \le 100), \ (M, \ m_i \le 10^7), \ (c_i \le 100)$
• 접근 1: Naive하게 접근해보자. 각 앱은 활성화/비활성화 상태 2가지이고 앱이 최대 100개이니 경우의 수는 $2^{100}=10^{30}$이므로 TLE!

접근2

• 접근 2: 재귀적 구조를 찾고, 중복이 발생하는지 찾아보자 (DP로 풀 수 있는지 확인)
  • 앱이 5개 있다고 가정했을 때 선택할 수 있는 모든 경우의 수를 구해보자
    • 1번째 앱을 선택했다면 (1, 0, 0, 0, 0) 등으로 표시하고, 그 노드로 인해 파생되는 경우의 수들을 연결하였다.

    • 

  • 위와 같으며 무수히 많은 중복이 발생하므로 DP를 적용할 수 있겠다.
  • dp[i]를 i번째 앱을 선택했을 때 구할 수 있는 가장 작은 cost라고 해보자 (우리가 구하려고하는 값은 cost이니)
  • 하지만 우린 byte 정보도 무시할 수 없으니 dp[i][j] 형태로 i번째 앱을 선택하고 j Byte 인 경우 중 가장 작은 cost라 정의하자
  • $dp[i][j] = \min_{k = i + 1 \ to \ n}(dp[k][j - cost[i]])$
    • i를 선택한 뒤, i + 1을 선택해보고, i + 2를 선택해보고, ... n을 선택해보고 중 가장 작은 cost를 구하기
  • 위와 같이 전형적인 Knapsack 형태의 점화식을 구할 수 있다.
• 제한 1: 하지만 $M \le 10^7$이기 때문에 최악의 경우 위 점화식의 공간복잡도는 $O(10^9)$ 이므로 MLE가 발생한다.
  • 따라서 주어진 문제를 해결할 수 없다. 시간복잡도 또한 $O(n \times n \times M) = 10^{11}$ 이므로 TLE가 발생한다.
• 의문점 1: $c_i \le 100$
  • 비용이 굉장히 작은데 이유가 있을까? 비용을 DP의 한 차원으로 넣어볼까?

접근3

• 접근 3: dp[i][j]를 i번째 앱을 선택했을 때 비용이 j인 경우 중 가장 큰 Byte라 정의하자
  • 가장 큰 Byte인 이유? 우리는 M Byte 이상의 앱을 비활성화 시켜야하기 때문에 같은 비용이라면 큰 용량을 줄이는게 맞다!
  • 점화식: $dp[i][j] = \max_{k = i + 1 \ to \ n }(dp[k][j - byte[i]])$
  • 시간 복잡도: $O(n^3 \cdot c) = 10^8$으로 이론상으로는 성공한다!
    • 이유? i의 최대치 100($n$), 모든 앱의 비용이 100($c$)이고 100($n$)개를 선택한 경우를 j의 최대치로 설정해야함, 이후 한 점당 n번 반복
    • 따라서 $n \times n \times c \times n$
• 최적화
  • 하지만 위에 점화식은 쓸데 없는 계산이 많다
  • dp[j]를 비용이 j인 경우 가장 큰 Byte로 정의해보면 어떨까?
  • $dp[j] = \max_{i = 1 \ to \ n}(dp[j - cost[i]])$
  • 시간 복잡도: $O(n^2 \cdot c)$

코드

// Baekjoon07579.cpp
#include <iostream>

using namespace std;

using pii = pair<int, int>;

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

    int n, m;
    cin >> n >> m;

    pii app[100]; // { byte, cost }
    int dp[10'001] = { 0, };
    for (int i = 0; i < n; i++)
        cin >> app[i].first;
    for (int i = 0; i < n; i++)
        cin >> app[i].second;

    for (int i = 0; i < n; i++) {
        for (int j = 10'000; j >= 0; j--) { // 0부터 증가하게 되면 자기 자신을 선택했던 경우의 수에 또 자기자신을 더하므로 중복!
            int cost = j - app[i].second;
            if (cost >= 0 && dp[cost] != 0)
                dp[j] = max(dp[j], dp[cost] + app[i].first);
        }
        dp[app[i].second] = max(dp[app[i].second], app[i].first);
    }

    int ans;
    for (int i = 0; i <= 10'000; i++) {
        if (dp[i] >= m) {
            ans = i;
            break;
        }
    }

    cout << ans << '\n';

    return 0;
}

잡담

• 저 모든 경우의 수 다이어그램은 GPT 시킴 GPT 짱!
• 거스름돈 문제(동전 문제)로 치환가능 할 것 같아 Greedy 일 수도? 라고 생각했지만 그러기 위해서는 각 앱의 byte가 배수 관계여야하기 때문에 반드시 DP 겠거니 생각이 들어 DP로 고정관념을 박고 시작했다.
• 전형적인 Knapsack 같지만 무게(Byte)를 차원으로 두면 안되는 생각이 필요한 Knapsack이다. 전형적인 Knapsack은 추후 포스팅하겠다!
• 내가 썼지만 뭐라고 썼는지 잘 모르겠다. 내 생각을 글로 표현하는 것은 역시 어렵다. 조금 더 많이 연습해야겠다.