경우의 수
동적 계획법
중복 되지 않는 경우의 수만으로 풀렸음.
https://www.acmicpc.net/problem/1535
문제 세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다. 세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하게 되면 L[i]만큼의 체력을 잃게 되고, J[i]만큼의 기쁨을 얻게 된다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다. 세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이 되거나, 음수가 되면, 죽게되서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N(<=20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 사람부터 순서대로 들어온다. |
code>>
#include<vector>
#include<algorithm>
using namespace std;
int GetPleasure(vector<int> *h, vector<int> *p, int _h, int idx)
{
if (idx == h->size()) return 0;
int pleasure = 0;
for (int i = idx; i < h->size(); i++)
{
if (_h - (*h)[i] <= 0) continue;
int temp = GetPleasure(h, p, _h - (*h)[i], i + 1);
pleasure = max(pleasure, (*p)[i] + temp);
}
return pleasure;
}
int main()
{
vector<int> h;
vector<int> p;
int input = 0;
scanf("%d", &input);
int data;
for (int i = 0; i < input; i++)
{
scanf("%d", &data);
h.push_back(data);
}
for (int i = 0; i < input; i++)
{
scanf("%d", &data);
p.push_back(data);
}
int result = GetPleasure(&h, &p, 100, 0);
printf("%d \n", result);
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
| 1966>프린터 큐 (0) | 2017.11.29 |
|---|---|
| 5557>1학년 (0) | 2017.11.29 |
| 11399>ATM (0) | 2017.11.26 |
| 5585>거스름돈 (0) | 2017.11.26 |
| 1874>스택 수열 (0) | 2017.11.25 |