2. 문제 요약: 세준이는 인사를 할 때마다 체력을 잃고, 기쁨을 얻는다. 체력이 0이 되지 않으면서 얻을 수 있는 기쁨을 최대값은?
3. 문제 접근 방법:
그 유명한 배낭 문제인데, 머리가 안 좋아서 이해하는 데 시간이 걸렸다.
인사할 사람의 수와 남아 있는 체력에 대한 정보를 가진 2차원 배열을 이용한다. 인사했다가 체력이 0이 되는 상황이면 이전의 기쁨 최대값을 유지하고, 그렇지 않으면 인사할 경우와 아닐 경우를 비교한다.
4. C 코드
(중간에 주석은 디버깅한다고 넣은 거라 무시해도 됨)
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
49
50
51
52
53
54
55
56
57
|
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int health = 100;
int N;
int L[21] = {0};
int J[21] = {0};
int dp[21][101] = {0};
scanf("%d", &N);
for(int i = 1; i <= N; i++)
scanf("%d", &L[i]);
for(int i = 1; i <= N; i++)
scanf("%d", &J[i]);
for(int i = 1; i <= N; i++)
{
for(int w = 1; w <= health; w++)
{
int temp = dp[i-1][w];
if(w - L[i] > 0)
{
dp[i][w] = max(temp, dp[i-1][w-L[i]] + J[i]);
}
else
{
dp[i][w] = temp;
}
/*
if(dp[i][w] == 55)
{
printf("*** i: %d, w: %d\n", i, w);
printf("temp: %d, J[i]: %d, dp: %d\n", temp, J[i], dp[i-1][w-L[i]]);
printf("dp[i][w]: %d\n", dp[i][w]);
break;
}
*/
}
}
printf("%d\n", dp[N][health]);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기