[프로그래머스] 피로도

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 12주차

 

프로그래머스 위클리 챌린지 마지막 문제입니다.

문제의 난이도가 일정하지 않은 점이나, 작성된 코드가 노출되어 좋아요를 받는 방식, 예전에 본 듯한 문제들 등이 좀 아쉽긴 했지만 이렇게 위클리 챌린지가 종료된다고 하니 이것도 아쉽네요.

 

문제 조건을 요약하면 다음과 같습니다.

• 맨 처음 주어진 피로도가 있다. 피로도는 던전을 접근할 때마다 감소한다.
• 각 던전에는 요구 피로도와 소모 피로도가 있다. 요구 피로도는 던전을 접근하기 위해 필요한 피로도의 최소 수치이며, 소모 피로도는 해당 던전을 접근할 경우 그 수치만큼 나의 피로도가 감소한다.
• 던전은 최소 1개, 최대 8개까지 존재한다.

 

던전의 개수가 매우 작은 만큼, 완전탐색을 하기에 어렵지 않습니다.

저는 재귀함수를 이용한 DFS식 완전탐색을 수행하였고, 탐색이 종료될 때마다 접근한 던전의 수를 구하고, 그 최댓값을 매번 갱신하여 정답으로 반환하였습니다.

 

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int dsize;
	int answer = 0;
	void dfs(int k, vector<bool> visited, vector<vector<int> > &d) {
	bool no_more = true;
	for (int i = 0; i < d.size(); i++) {
	if (visited[i]) continue;
	if (k >= d[i][0]) {
	no_more = false;
	k -= d[i][1];
	visited[i] = true;
	dfs(k, visited, d);
	k += d[i][1];
	visited[i] = false;
	}
	}
	//접근한 새로운 던전이 없는 경우
	if (no_more) {
	int temp = dsize;
	for (int i = 0; i < visited.size(); i++) {
	if (!visited[i]) temp--;
	}
	answer = max(answer, temp);
	}
	}
	int solution(int k, vector<vector<int>> dungeons) {
	dsize = dungeons.size();
	vector<bool> visited;
	//방문 배열 초기화
	for (int i = 0; i < dsize; i++) {
	visited.push_back(false);
	}
	//모든 던전에 대해 시작점 i를 기준으로 완전탐색을 시작한다 (재귀함수).
	for (int i = 0; i < dungeons.size(); i++) {
	if (k >= dungeons[i][0]) {
	visited[i] = true;
	k -= dungeons[i][1];
	dfs(k, visited, dungeons);
	visited[i] = false;
	k += dungeons[i][1];
	}
	}
	return answer;
	}

view raw 피로도.cpp hosted with ❤ by GitHub

 

채점 결과

데이터의 개수 제한과 조건을 생각해 본다면 완전 탐색을 어렵지 않게 떠올릴 수 있었습니다.

완전탐색 외에 처음에 떠오를 법한 방법은 그리디 혹은 DP인데, 요구 피로도와 소모 피로도가 별개의 값인 만큼 이 두 방법으로의 접근은 쉽지 않은 것 같습니다.