(C++) - 백준(BOJ) 1535 : 안녕?

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

1535번: 안녕

기본 전수조사 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

사람 수 n, 잃는 체력 l, 얻는 기쁨 j를 일차원 배열로 선언 후 적절히 입력받습니다.

📔 풀이과정

dfs함수를 수행합니다. 현재 depth번째 사람에게 다름 두 가지 상태가 있습니다.1. depth번째 사람에게 인사하기2. depth번째 사람에게 인사하지 않기각자에 대해 모든 경우를 조사한 시간복잡도는 2^20이 되게 됩니다.

📔 정답출력

dfs함수의 결과를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, l[21], j[21];

int dfs(int depth, int curStrength, int happy){
    if(curStrength <= 0) return 0;
    if(depth == n + 1){
        return happy;
    }
    int ans = 0;
    ans = max(ans, dfs(depth + 1, curStrength - l[depth], happy + j[depth]));
    ans = max(ans, dfs(depth + 1, curStrength, happy));
    return ans;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> l[i];
    for(int i = 1; i <= n; i++) cin >> j[i];
    cout << dfs(0,100,0);
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.