#문제
https://www.acmicpc.net/problem/4781
4781번: 사탕 가게
문제 상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 누가 더 건강이 안 좋아질 수 있는지 내기를 하자고 했다. 상근이는 내기를 그 즉시 받아들였다. 두 사람은 같은 돈을 가지고 가게에 들어가서 사탕을 산다. 이때, 구매한 사탕의 칼로리가 더 큰 사람이 내기에서 이기게 된다. 상근이는 잠시 화장실에 갔다온다고 핑계를 댄 뒤에,
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
|
#include <iostream>
using namespace std;
int n, M;
// M : m*100 (dp 배열의 인덱스로 가격을 사용하기 위해.)
int candy[5000][2];
// [0] : 칼로리
// [1] : 가격*100
int dp[10001];
// 0 ~ 10000을 사용한다.
int main(){
while(true){
double m;
cin>>n>>m;
if( n==0 ) break; // 0 0.00을 입력받으면 테스트케이스 입력을 끝마친다.
M = (int)(m*100+0.5);
// n개의 사탕 정보 저장
for(int i=0; i<n; i++){
int c, P; double p;
cin>>c>>p;
P = (int)(p*100+0.5);
candy[i][0] = c;
candy[i][1] = P;
}
fill_n(dp, 10001, 0);
// 돈 m을 가지고 구매할 수 있는 최대 칼로리를 구한다.
for(int i=0; i<n; i++){
int cal = candy[i][0];
for(int ii= candy[i][1]; ii<=M; ii++){
dp[ii] = max(dp[ii], dp[ii-candy[i][1]]+cal);
}
}
// 최대 칼로리를 찾아 출력한다.
int result=0;
for( int i=0; i<10001; i++ ){
result = max(result, dp[i]);
}
cout<<result<<'\n';
}
return 0;
}
|
cs |
##
7579번 문제와 유사하다는 글을 읽고 복습할 겸 풀어보았다.
'BOJ' 카테고리의 다른 글
| BOJ 10942번 :: 팰린드롬? (0) | 2020.01.28 |
|---|---|
| BOJ 2261번 :: 가장 가까운 두 점 (0) | 2020.01.27 |
| BOJ 7579번 :: 앱 (0) | 2020.01.23 |
| BOJ 1520번 :: 내리막 길 (0) | 2020.01.09 |
| BOJ 12015번 :: 가장 긴 증가하는 부분 수열 2 (0) | 2020.01.06 |