백준: 1106. 호텔 (C++)

1. 문제 정보

• https://www.acmicpc.net/problem/1106
• Gold IV
• 다이나믹 프로그래밍

 

2. 문제 풀이

 

전형적인 배낭 문제 유형이에요 !
하지만 이번 문제를 풀면서 풀이 과정을 개선한 점, 그리고 새롭게 배운 점이 있어 정리해볼까 해요 🥰

 

• 2차원 배열 풀이
  원래 저는 배낭 문제를 풀 때 2차원 배열 형태로 풀어왔었어요
  첫 번째 예시를 예로 들어봅시다
  
  먼저 DP 배열은 DP[1001][100001]로 작성해줬어요
  N이 1000보다 작거나 같고, 각 도시에서 낼 수 있는 비용이 최대 100이므로
  C = 1000일 때 필요한 최대 비용은 100 * 1000이 됩니다
  
  이에 맞춰 예제 입력 1번에 대한 풀이를 해볼게요
  
  

  

  
  초기에는 이와 같은 2차원  배열로 시작합니다
  1번 도시의 경우, 3의 홍보 비용으로 5의 고객을 유치할 수 있어요
  이를 테이블에 반영하게 되면
  
  

  

  
  이러한 상태가 됩니다
  우리가 구하고 싶은 값은 최소 12명을 유치하는 최솟값이기 때문에, 현재까지 최소 비용은 9가 되겠네요 😊
  
  이제 2번 도시도 반영해보도록 하겠습니다
  
  

  

  
  일단 비용이 3일 때까지만 반영해보도록 합시다
  이때 2번 도시에서 비용 3으로 얻을 수 있는 고객 수는 3이 되겠죠?
  하지만 우리가 구하고 싶은 것은 비용으로 얻을 수 있는 최대 고객 수잖아요?
  때문에 이전까지 도시에서 얻을 수 있는 최대 고객 수와 현재 도시에서 얻을 수 있는 최대 고객 수를 비교해줍니다
  이에 맞춰서 5를 반영하게 된 것이에요 😀
  점화식으로 보자면 DP[i][j] = DP[i - 1][j]가 된 것이지요
  
  계속 이어나가 보겠습니다
  
  

  

  
  이번엔 비용을 4 투자했을 때 상황입니다
  2번 도시만 반영했을 때는 4, 1번 도시만 반영했을 때는 5가 되겠죠?
  하지만 이 때 1번 도시와 2번 도시를 동시에 반영하고 싶다면 어떻게 해야 할까요?
  
  현재까지 사용한 비용에서 현재 도시 비용의 가격을 제했을 때 가치을 참고하면 됩니다
  점화식으로 보자면 DP[i][j] = DP[i][j - cost[i]] + customer[i]가 되겠죠
  현재 상태를 기준으로 보자면 DP[2][4] = DP[2][4 - 1] + 1 = DP[2][3] + 1 = 5 + 1 = 6이 되는거지요 👀
  이 두 가지 경우를 합치게 되면, 점화식은 이와 같이 되게 됩니다
  DP[i][j] = max(DP[i - 1][j], DP[i][j - cost[i]] + customer[i])
  이때 배열이 음수가 되면 안되므로, j >= cost[i]일 때만 가능하도록 해야겠죠 😊
  
  이와 같은 방식으로 배열을 계속 채워나갑니다
  
  

  

  
  채워 나가다 보면, 우리가 구하고자 하는 최소 인원 수에 딱 맞는 비용이 나타나네요 !
  즉, 답은 8이 됩니다 🥰
  
  

   
  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  #define INF (int)2e9
  
  int ans = INF;
  int c, n;
  int dp[21][1000001];
  vector<pair<int, int>> v;
  
  int main() {
      ios_base::sync_with_stdio(0);
      cin.tie(0);
  
      cin >> c >> n;
      v.resize(n + 1);
  
      for (int i = 1; i <= n; i++) {
          cin >> v[i].first >> v[i].second;
      }
  
      for (int i = 1; i <= n; i++) {
          for (int j = 0; j <= 1000000; j++) {
              if (j >= v[i].first) {
                  dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i].first] + v[i].second);
              }
              else {
                  dp[i][j] = dp[i - 1][j];
              }
  
              if (dp[i][j] >= c) {
                  ans = min(ans, j);
                  break;
              }
          }
      }
  
      cout << ans;
  }
   

  
  

  

  
  통과는 했지만, 메모리 사용량이 상당히 높네요 . . !
  풀이를 봤을 때 더 간단히 1차원 배열로도 가능해 보이지 않나요?
  이제 이 부분에 대해 정리해볼게요 !
  
  
• 1차원 배열 풀이
  이 문제는 사실 1차원 배열로도 풀 수 있어요 😊
  이 부분에 대해 살짝 정리를 해보자면
  
  특수한 조건이 없을 때, 0-1 배낭 문제나 무한 배낭 문제의 경우 1차원 배열로 풀이가 가능합니다
  
  이번 문제는 단순히 목표 인원수만 계산하는 무한 배낭 문제이기 때문에 역시 1차원 배열로 풀이가 가능합니다
  풀이는 사실상 거의 동일한데, 배열에서 몇 번 도시냐를 나타내는 차원은 필요가 없을 것 같아요 👀
  때문에 DP[100001]로 형태를 변경해줍니다
  그리고 하던대로 배열의 앞에서부터 순차적으로 적용해주면 1차원 배열로만 갱신이 가능합니다
  
  

   
  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  #define INF (int)2e9
  
  int ans = INF;
  int c, n;
  int dp[1000001];
  vector<pair<int, int>> v;
  
  int main() {
      ios_base::sync_with_stdio(0);
      cin.tie(0);
  
      cin >> c >> n;
      v.resize(n + 1);
  
      for (int i = 1; i <= n; i++) {
          cin >> v[i].first >> v[i].second;
      }
  
      for (int i = 1; i <= n; i++) {
          for (int j = 0; j <= 1000000; j++) {
              if (j >= v[i].first) {
                  dp[j] = max(dp[j], dp[j - v[i].first] + v[i].second);
  
                  if (dp[j] >= c) {
                      ans = min(ans, j);
                      break;
                  }
              }
          }
      }
  
      cout << ans;
  }
   

  
  

  

  
  어떤가요? 코드도 훨씬 짧아졌고, 메모리도 크게 줄일 수 있게 되었죠?
  이런 방식으로도 풀 수 있답니다 😊
  
  이때 0-1 배낭과 무한 배낭의 1차원 풀이의 차이점은 반영 순서에 있는데요 !
  무한 배낭의 경우 앞에서부터 차례대로 갱신하게 되면 이와 같이 갯수가 몇 개든 자동적으로 반영이 되죠?
  하지만 0-1 배낭의 경우 이렇게 적용하면 안되므로, 배낭 반영을 역순으로 해야해요
  이렇게 하면 하나의 물건에 대해서만 반영할 수 있답니다 🥰