[Algorithm]Baekjoon 16194번 :: 카드 구매하기 2

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

16194번: 카드 구매하기 2

 

 
int n;
int arr[1001] = { 0 };
int dp[1001] = { 0 };
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
 
    memset(dp, 0x3f, sizeof(dp));
 
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = arr[i];
 
        for (int j = 1; j <= i / 2; ++j)
        {
            dp[i] = min(dp[i], dp[j] + dp[i - j]);
        }
    }
    
    cout << dp[n];
}
 

 

배낭문제의 하위호환느낌의 문제이다.

i개를 사려할 경우의 최솟값을 dp테이블에 갱신한다.

dp[i]에 arr[i]값을 먼저 넣은 후,(n개짜리를 한번에 사는 경우의 수) 아래의 비교들을 통해 최솟값을 dp테이블에 갱신한다.

 

만약 5개를 사려한다면 dp[1] + dp[4] , dp[2] + dp[3], dp[3] +dp[2], dp[4] + dp[1] 의 경우의 수가 나올것이고, 이 중 최솟값을 선택하면 된다.

여기서 인덱스 j의 반복문을 돌 때는 최대 i/2번만 돌면 된다.

위의 경우의 수를 보면, dp[1] + dp[4] 와 dp[4] + dp[1] 의 두가지가를 봤을 때 사실 똑같은 값이기 때문이다.

마찬가지로 dp[2] + dp[3]이랑 dp[3] + dp[2]도 같은 맥락이다.

그렇기 때문에 굳이 최대 i번까지 할필요없고, i/2까지만 하면 된다.