백준 1535. 안녕

안녕

DFS 대표 문제 퇴사와 유사한 문제

1. 간단 설명

---

N명의 사람이 방문안을 왔다

인사를 하면 체력을 잃는다

체력을 잃는 대신 기쁨을 얻는다

체력이 허락하는 한 인사를 하고 얻을 수 있는 최대 기쁨을 출력하는 문제

2. 예시

---

3명의 방문객
잃는 체력 : 1 21 79
얻는 기쁨 : 20 30 25

시작 체력은 100이므로

(1), (21), (79), (1,21), (1,79), (21,79), (1, 21, 79)로 각각 시도해본다

체력이 0이거나 음수로 떨어지면 불가능하므로 (21,79), (1, 21, 79) 는 불가능하므로

(1, 21)일때 얻을 수 있는 기쁨이 50으로 가장 크다

3. 알고리즘

---

처음 생각한 알고리즘

1. N, damage, price를 입력받는다
2. 1명만 볼 경우, 2명 볼 경우, ... , N명 볼 경우를 DFS 돌려본다
3. DFS(지금 몇명본건지, 몇명 볼건지, 남은 체력, 얻은 기쁨)
	3-1. 만약 남은 체력이 0이하라면 리턴
	3-2. 모든 사람을 봤다면, 현재 얻은 기쁨과 기록된 최대 기쁨을 비교 후 리턴
	3-3. i~N 사이에서 다음 값을 뽑는다
		3-3-1. 만약 이미 뽑은 사람이라면 패스한다
		3-3-2. 아니라면, 이 사람을 뽑아서 DFS를 재호출한다
		DFS(뽑은사람 수 + 1, 몇명 볼건지, 남은체력 - 이사람이 주는 체력피해, 현재 얻은 기쁨 + 이사람이 주는 기쁨)

이 방법은 10명까지 정도는 가능한데, 12명을 넘는 케이스에서는 시간초과가 발생했다

1명 뽑는경우, 2명 뽑는경우, … 12명 뽑는경우를 모두 체크해야하므로 시간초과 발생

DP로 처리할수도 있겠지만 더 좋은 방법이 있으므로 이 방법으로 시도함

DFS(int level, int max_level, int hp, int sum){
	1. 체력이 0 이하로 떨어지면 리턴
	2. 다 뽑았으면 결과값 비교 후 갱신, 이후 리턴
	3. 현재 레벨의 사람을 뽑을것인지 말것인지를 DFS로 결정
		DFS(level + 1, hp, sum) 안만나는 
		DFS(level + 1, hp - damage[level], sum + price[level) 만나는 경우
}

첫번째 사람부터 이사람을 만날지 만나지 않을지로 접근하는 것

N명을 세워놓고 1번부터 N번까지 이사람을 만날지 안만날지 선택하면서 DFS를 돌린다

필요 변수

• 사람 수 int N (1 ≤ N ≤21)
• int damage[21], int price[21] 이사람이 주는 데미지와 기쁨 (0≤ 체력, 기쁨 ≤ 100)
• 최대 기쁨 int max_res
  • 20명이 100의 기쁨을 줘도 int 내에서 처리 가능

4. 소스코드

---

#include <iostream>

#define MAX 21

using namespace std;

int N;
int damage[MAX], price[MAX];
int max_res = 0;

void Input() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> damage[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> price[i];
	}

}

void DFS(int level, int hp, int sum) {
	if (hp <= 0) return;
	if (level == N) {
		if (sum > max_res) {
			max_res = sum;
		}
		return;
	}
	DFS(level + 1, hp - damage[level], sum + price[level]);
	DFS(level + 1, hp, sum);
}

int main() {
	Input();

	DFS(0, 100, 0);

	cout << max_res;

	return 0;
}