[백준/C++] 1535번: 안녕

문제

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

1535번: 안녕

---

문제 요약

1 ~ N번까지 N명의 사람이 있다.

 

세준이가 i번 사람에게 인사를 하면, L[i]만큼 체력을 잃고, J[i]만큼의 기쁨을 얻는다.

 

세준이는 각각의 사람에게 최대 1번만 말할 수 있다.

 

현재 세준이의 체력은 100이고, 기쁨은 0이다.

 

만약 세준이의 체력이 0이나 음수가 되면 죽어서 아무런 기쁨을 느끼지 못한다.

 

세준이가 얻을 수 있는 최대 기쁨을 출력한다.

---

코드

#include <iostream>
#include <algorithm>

#define MAX_N 20

using namespace std;

int n, res;

int health_lose[MAX_N + 1];
int pleasure_get[MAX_N + 1];


void dfs(int num, int health, int pleasure) {

	// 체력이 0 이하 거나, n + 2번째 인덱스 (n + 1번째 사람)에 접근하려고 하면 리턴
	if (health <= 0 || num > n + 1) {
		return;
	}

	// res 갱신
	res = max(res, pleasure);

	// num번째 사람과 악수할 경우
	dfs(num + 1, health - health_lose[num], pleasure + pleasure_get[num]);

	// num번째 사람과 악수하지 않을 경우
	dfs(num + 1, health, pleasure);
}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> health_lose[i];
	}

	for (int i = 1; i <= n; i++) {
		cin >> pleasure_get[i];
	}

	// 0은 아직 아무와도 악수를 하지 않은 상태 -> 백트래킹 탐색
	dfs(0, 100, 0);

	cout << res;
}

---

코드 설명

완전 탐색 (백트래킹)을 이용하여 문제를 해결한다.

 

첫 번째 사람부터 N번째 사람까지 악수를 하고 다음 사람으로 넘어 가거나, 하지 않고 넘어 가는 두 가지로 나눠 경우의 수를 탐색한다. 

 

탐색 중, 체력이 0이 되거나, N + 1번째 사람과 악수를 하려고 한다면 반환한다. (백트래킹)

---

고찰

다음 악수할 사람을 반복문을 이용해 1번부터 N번까지 모두 탐색할 경우, 시간 초과가 발생했다.

 

고민 결과, 첫 번째 사람부터 N번째 사람까지 올라가면서 체크하면 모든 경우의 수를 탐색할 수 있다는 사실을 깨달았다.