Algorithm/Baekjoon

[Algorithm]Baekjoon 1535번 :: 안녕

MaxLevel 2024. 1. 24. 20:32

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

 

1535번: 안녕

첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
 
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];
}
 
 
 
 cs

 

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

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