(2293) 동전 1

https://www.acmicpc.net/problem/2293

단계별로 풀어보기

31단계(동적 계획법 2) 5번째

 

 

 

냅색 문제처럼 dp[a][b]를 a번째 종류의 동전까지 썼을 때 b원을 만드는 경우의 수로 두고 풀면 되는데... 메모리 제한이 빡빡하다.

대부분의 문제는 시간 복잡도만 고려하면 되지 공간 복잡도는 고려할 필요가 없지만, 이렇게 공간 복잡도를 고려해야 하는 경우가 있다.

그런데 이미 RGB거리와 평범한 배낭에서 필요없는 값을 저장하지 않고 메모리를 절약하는 테크닉에 대해 얘기한 적 있다.

차원 하나를 줄여 dp[b]를 b원을 만드는 경우의 수로 두고 풀면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n >> k;
  
  vector<int> dp(k+1);
  
  dp[0]= 1;
  
  while(n--){
    int v;
    
    cin >> v;
    
    for(int i=k;i>=0;i--){
      if(!dp[i])  continue;
      
      for(int j=v;i+j<=k;j+=v){
        dp[i+j]+= dp[i];
      }
    }
  }
  
  cout << dp[k];
  
  return 0;
}