[1535번] 안녕

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 재귀

재귀를 통해 문제를 해결 할 수 있다.

n제한이 20이기에 체력이 0이하로 떨어지는 것에 대해 최적화를 시켜주고 모든 경우에 대해 재귀를 돌려본 후 최대 행복도를 찾는다.

소스 코드 : 

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 58 59 60

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   int life[22]; int happy[22]; int n; int ans; void dfs(int i, int nowLife, int nowHappy) {     for (i = i + 1; i < n; i++)     {         if (nowLife - life[i] <= 0)             continue;           ans = max(nowHappy + happy[i], ans);         dfs(i, nowLife - life[i], nowHappy + happy[i]);     } } int main() {     scanf("%d", &n);       for (int i = 0; i < n; i++)         scanf("%d", &life[i]);       for (int i = 0; i < n; i++)         scanf("%d", &happy[i]);       for (int i = 0; i < n; i++)     {         if (100 - life[i] <= 0)             continue;           ans = max(0 + happy[i], ans);           dfs(i, 100 - life[i], 0 + happy[i]);     }       cout << ans;          return 0; }         if (once)         {             ans = min(ans, mid);             end = mid - 1;         }         else             start = mid + 1;     }       cout << ans << endl;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus