[프로그래머스] 완전탐색 - 피로도

문제

풀이

#include <string>
#include <vector>
using namespace std;

int s;
int answer = 0;
vector<bool> visited;

void dfs(int len, int count, int HP, vector<vector<int>> dungeons){
    if(len == s){
        answer<count?answer=count:answer;
        return;
    }
    
    for(int i=0; i<s; i++){
        if(!visited[i]){
            visited[i] = true;
            if(HP < dungeons[i][0])
                dfs(len+1, count , HP-dungeons[i][1],dungeons);
            else
                dfs(len+1, count+1, HP-dungeons[i][1],dungeons);
            visited[i] = false;
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    
    s = dungeons.size();
    visited.assign(8,false);
    dfs(0,0,k,dungeons);

    return answer;
}

 

순열을 활용한 완전탐색을 사용해야겠다고 생각했기때문에 깊이우선탐색(dfs)을 활용하였다.

 

 

 

 

다른 사람 풀이

#include <vector>
using namespace std;

int solution(int k, vector<vector<int>> d) {
    int ans = 0;
    for (auto it = d.begin(); it != d.end(); it++) {
        if (k >= (*it)[0]) {
            auto d2 = vector(d.begin(), it);
            d2.insert(d2.end(), it+1, d.end());

            int s = solution(k - (*it)[1], d2) + 1;
            ans = s > ans ? s : ans;
        }
    }
    return ans;
}

auto d2 = vector(d.begin(), it);

코드의 위 부분을 이해를 못하고있다. 인자가 2개인 벡터 ...

알게되면 다시 수정하여 적도록 하겠다!

 

vector.insert

vector.insert(const_iterator position, InputIterator first, InputIterator last)

• position : 원소를 추가할 위치
• first : 추가할 원소들의 시작위치
• last : 추가할 원소들의 마지막 위치
• first부터 last까지의 원소가 position뒤에 추가된다.

 

 

다른 사람 풀이 2

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int answer = 0;
vector<vector<int>> dungeons;
int N;

int visit[8];
void dfs(int h, int p){
    if(answer < h)
        answer = h;

    for(int i=0; i<N; i++){
        if(visit[i] || dungeons[i][0] > p)
            continue;

        visit[i] = 1;
        dfs(h+1, p-dungeons[i][1]);
        visit[i] = 0;
    }
}

int solution(int k, vector<vector<int>> dungeons_) {
    dungeons = dungeons_;
    N = dungeons.size();

    dfs(0, k);

    return answer;
}

같은 깊이탐색을 이용했지만, 위의 코드에 비해 나의 코드가 좀더 복잡한 것 같다.

너무 알고리즘을 복잡하게 생각했거나 dfs 원리를 이해 못한것같다.

 

코드를 살짝 수정해주었다!

/* 수정 전 */
if(len == s){
	answer<count?answer=count:answer;
	return;
}

/* 수정 후 */
if(answer < count) answer = count;

 

 

 

 

 

---

https://novlog.tistory.com/255

[C++] vector.insert 멤버함수를 이용해 두 벡터 연결하기

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges