https://school.programmers.co.kr/learn/courses/30/lessons/87946
사실 처음 봤을 때에는 그리디나 DP로 접근해야할 것 같았는데, 개수가 생각보다 많지 않아서, 완전탐색으로 진행해도 무방할 것 같았다. 모든 경우를 따지기 위해, C++의 next_permutation함수를 통해 순열을 구성했고, 이를 통해 모든 경우를 탐색했다.
#include <bits/stdc++.h>
#define ALL(X) X.begin(),X.end()
using namespace std;
int solution(int k, vector<vector<int>> dungeons) {
int answer = -1;
int curr_fat;
int cnt;
sort(ALL(dungeons));
do {
cnt = 0;
curr_fat = k;
for(auto& elem : dungeons) {
if (curr_fat < elem[0]) break;
curr_fat -= elem[1];
cnt++;
}
answer = max(cnt, answer);
} while(next_permutation(ALL(dungeons)));
return answer;
}
'coding_test > programmers' 카테고리의 다른 글
lv2 / n^2 배열 자르기 / C++ (0) | 2022.09.19 |
---|---|
lv1 / 로또의 최고 순위와 최저 순위 / C++ (0) | 2022.09.15 |
lv1 / 성격 유형 검사 / 카카오 / C++ (2) | 2022.09.13 |
lv2 / 양궁대회 / 카카오 / C++ (0) | 2022.09.08 |
lv2 / K진수에서 소수 개수 구하기 / 카카오 / C++ (0) | 2022.09.01 |