[Algorithm]Baekjoon 1535번 :: 안녕

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

1535번: 안녕

 
 
int n;
int staminas[21];
int happiness[21];
int dp[21][100] = { 0 }; // 물건, 체력
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> staminas[i];
    }
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> happiness[i];
    }
 
    for (int i = 1; i <= n; ++i)
    {
        int stamina = staminas[i];
        int happy = happiness[i];
 
        for (int j = 0; j <= 99; ++j) // 체력
        {
            if (j >= stamina) // 인사할 체력되면
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stamina] + happy);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
 
    cout << dp[n][99];
}
 
 
 

 

배낭문제를 아주 조금만 응용해서 풀면 된다.

체력은 0이되면 안되며, 소모할체력이 0인값이 들어올수도 있기 때문에 0부터 99까지 반복문을 돌아주면 된다.