Baekjoon 16194번: 카드 구매하기2

 

11052번의 응용문제이다.

반대로 min 값을 구하면 된다.

 

11052번의 코드를 보면,

 

#include <iostream>
#include <math.h>

using namespace std;

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

    int n; //4
    cin>>n;
    int *dp=new int[n+1]; // 최대비용값을 넣는다
    int *pack=new int[n+1]; // 팩의 가격

    for(int i=1;i<=n;i++){
        cin>>pack[i]; // 1 5 6 7 
    }
    
    dp[0]=0;
    pack[0]=0;

    for(int i=1;i<=n;i++){
        for (int j=1;j<=i;j++){
            dp[i]=max(dp[i], dp[i-j]+pack[j]);
        }
    }
    cout<<dp[n];

    delete[] dp;
    delete[] pack;
}

 

동적할당을 하면서 배열 dp의 모든 값이 0으로 들어가는 것을 알 수 있었다!

단지 max-> min값으로 바꾼 후 컴파일 하면 모든 결과 값이 0으로 나오므로 원하는 값을 얻을 수 없다는 것이었다.

 

그러므로 배열 dp의 초기값을 INT_MAX로 설정하고 실행하였다.

 

#include <iostream>
#include <math.h>
#include <limits.h> //헤더추가

using namespace std;
//카드 구매하기2, 최소비용

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

    int n; 
    cin>>n;
    int *dp=new int[n+1];
    int *pack=new int[n+1];

    for(int i=1;i<=n;i++){
        cin>>pack[i]; 
    }

// 추가한 부분
    for(int i=1;i<=n;i++){
        dp[i]=INT_MAX;
    }
    
    dp[0]=0;
    pack[0]=0;


    for(int i=1;i<=n;i++){
        for (int j=1;j<=i;j++){
            int tmp1=dp[i];
            int tmp2=dp[i-j]+pack[j];
            dp[i]=min(dp[i], dp[i-j]+pack[j]);
        }
    }
    cout<<dp[n];

    delete[] dp;
    delete[] pack;
}