[프로그래머스] 피로도

2022. 6. 30. 18:42·알고리즘 이론/백준

풀이 : 

처음 접근했을 떄, 생각난 방법은 필요 피로도는 내림차순 소모 피로도는 오름차순으로 정렬 후 

그리디로 접근하는 방법을 생각했다. 하지만 조건을 확인해보니, 던전이 8개로 제한 되있다.

때문에 안전하게 모든 경우의 수를 모두 탐색하는 방법으로 선택하였다.

 

 

방법 1) 

 

- next_permutation 

모든 경우의 순열을 만들도록 사용했다 

 

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

void permutation(int k, vector<vector<int>>& dungeons, int & answer){
    vector<int> per;
    int tempK = k;
    for(int i=0;i<dungeons.size();i++){
        per.push_back(i);
    }
    do{
        tempK = k;
        for(int i=0; i<per.size();i++){
            int next = per[i];
            int minValue = dungeons[next][0];
            int consumeValue = dungeons[next][1];
            
            if(tempK>=minValue){
                tempK-= consumeValue;
                answer = max(answer,i+1);
                
            }else break;
            
        }
        
    }while(next_permutation(per.begin(), per.end()));
    
 
   
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer =-1;
    permutation(k, dungeons, answer);
    return answer;
    
    
    
}

 

방법 3) DFS로 접근하는 방법

#include <string>
#include <vector>
#include <queue>
int answer = 0;
bool check[9]= {false,};
using namespace std;
void DFS(int now, int k, vector<vector<int>> dungeons){
    if(answer < now) answer= now;
    for(int i=0;i < dungeons.size();i++){
        if(check[i] || dungeons[i][0] > k) continue;
        check[i] =true;
        DFS(now+1, k-dungeons[i][1], dungeons);
        check[i]= false;
        
    }
    
}

int solution(int k, vector<vector<int>> dungeons) {
    
    DFS(0,k, dungeons);
    return answer;
}
저작자표시 비영리 (새창열림)

'알고리즘 이론 > 백준' 카테고리의 다른 글

[백준] 11059 크리 문자열 c++  (1) 2021.06.26
[5032] 탄산 음료 C++  (0) 2021.06.26
[백준] 2863 이게 분수?  (1) 2021.06.26
[백준] 1427 소트인사이드 c++  (0) 2021.06.26
[백준] 1065 한수 c++  (0) 2021.06.26
'알고리즘 이론/백준' 카테고리의 다른 글
  • [백준] 11059 크리 문자열 c++
  • [5032] 탄산 음료 C++
  • [백준] 2863 이게 분수?
  • [백준] 1427 소트인사이드 c++
senyalog
senyalog
개발 블로그 https://github.com/iamyunjuda
  • senyalog
    Senya의 개발 블로그
    senyalog
  • 전체
    오늘
    어제
    • 분류 전체보기 (77)
      • 일상 (6)
      • 알고리즘 이론 (14)
        • 백준 (8)
      • 개발 (47)
        • Server (7)
        • 인턴 (11)
        • Javascript (0)
      • 경제 (4)
  • 블로그 메뉴

    • Github
    • 홈
  • 링크

    • Github
  • 공지사항

  • 인기 글

  • 태그

    개발
    공부
    공대생
    GIT
    컴공
    깃
    백준
    카페
    백준풀이
    코딩
    개발자
    생각
    경제
    개발공부
    C++
    인턴
    MSA
    nestjs
    코딩테스트
    알고리즘공부
    대학생
    일상
    TypeScript
    백엔드
    서버
    백준문제
    인턴생활
    대학생인턴
    이마고웍스
    알고리즘
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
senyalog
[프로그래머스] 피로도
상단으로

티스토리툴바