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

1535번 안녕

문제 링크

안녕

분석

체력이 0이하가 되면 안됩니다.

기쁨의 최대값을 구해야합니다.

배낭 문제(knapsack problem)와 유사한 동적 계획법(DP/Dynamic Programming)으로 푸는 문제입니다.
체력 소모를 아이템의 무게, 기쁨을 아이템의 가치로 볼 수 있습니다.
즉, 최대 무게가 99인 배낭에 아이템을 넣어 최대 가치를 구하는 문제와 같은 개념입니다.

N(총 사람 수)이 크지 않아서 브루트 포스로도 풀이할 수 있습니다.

풀이

브루트 포스를 기반으로 한 DFS를 사용해서 풀이해보았습니다.

#include <iostream>
#include <vector>
#include <algorithm>

int people; // 사람 수
std::vector<int> cost; // 각 사람에게 인사할 때 소모되는 체력
std::vector<int> happy; // 각 사람에게 인사할 때 얻는 기쁨

// 현재 index번째 사람부터 시작해 남은 체력과 누적 기쁨으로 얻을 수 있는 최대 기쁨을 계산하는 DFS 함수
int dfs(int index, int health, int pleasure)
{
	// 종료 조건으로, 모든 사람을 다 확인했거나 체력이 0이하인 경우
	if (index == people) return pleasure;
	if (health <= 0) return 0;

	// 해당 사람에게 인사하지 않는 경우
	int pass = dfs(index + 1, health, pleasure);

	// 체력이 충분해서 해당 사람에게 인사하는 경우
	int pick = 0;
	if (health - cost[index] > 0)
	{
		pick = dfs(index + 1, health - cost[index], pleasure + happy[index]);
	}

	int answer = std::max(pass, pick);
	return answer;
}

int main()
{
	// 총 인원을 입력 받는다.
	std::cin >> people;

	// 소모되는 체력을 입력받고, 저장한다.
	for (int i = 0; i < people; ++i)
	{
		int temp;
		std::cin >> temp;
		cost.push_back(temp);
	}

	// 얻는 기쁨을 입력받고, 저장한다.
	for (int i = 0; i < people; ++i)
	{
		int temp;
		std::cin >> temp;
		happy.push_back(temp);
	}

	// dfs를 통해 최대 행복을 구한다.
	int answer = dfs(0, 100, 0);
	std::cout << answer;
}

성능 요약

시간 복잡도는 $O(2^n)$입니다.

• 입력 반복문 $O(n) + O(n) \approx O(n)$
• DFS $O(2^n)$
• $O(n) + O(2^n)$

공간 복잡도는 $O(n)$입니다.

• 입력 데이터를 저장하는 벡터 std::vector<int> cost, std::vector<int> happy $O(n) + O(n) \approx O(n)$
• 재귀 호출 스택 $O(n)$
• $O(n) + O(n)$

메모리: 2020 KB

시간: 4 ms