https://school.programmers.co.kr/learn/courses/30/lessons/87946
λ¬Έμ μ€λͺ
XXκ²μμλ νΌλ‘λ μμ€ν (0 μ΄μμ μ μλ‘ ννν©λλ€)μ΄ μμΌλ©°, μΌμ νΌλ‘λλ₯Ό μ¬μ©ν΄μ λμ μ ννν μ μμ΅λλ€. μ΄λ, κ° λμ λ§λ€ ννμ μμνκΈ° μν΄ νμν "μ΅μ νμ νΌλ‘λ"μ λμ ννμ λ§μ³€μ λ μλͺ¨λλ "μλͺ¨ νΌλ‘λ"κ° μμ΅λλ€. "μ΅μ νμ νΌλ‘λ"λ ν΄λΉ λμ μ νννκΈ° μν΄ κ°μ§κ³ μμ΄μΌ νλ μ΅μνμ νΌλ‘λλ₯Ό λνλ΄λ©°, "μλͺ¨ νΌλ‘λ"λ λμ μ ννν ν μλͺ¨λλ νΌλ‘λλ₯Ό λνλ λλ€. μλ₯Ό λ€μ΄ "μ΅μ νμ νΌλ‘λ"κ° 80, "μλͺ¨ νΌλ‘λ"κ° 20μΈ λμ μ νννκΈ° μν΄μλ μ μ μ νμ¬ λ¨μ νΌλ‘λλ 80 μ΄μ μ΄μ΄μΌ νλ©°, λμ μ ννν νμλ νΌλ‘λ 20μ΄ μλͺ¨λ©λλ€.
μ΄ κ²μμλ ν루μ ν λ²μ© ννν μ μλ λμ μ΄ μ¬λ¬κ° μλλ°, ν μ μ κ° μ€λ μ΄ λμ λ€μ μ΅λν λ§μ΄ νννλ € ν©λλ€. μ μ μ νμ¬ νΌλ‘λ kμ κ° λμ λ³ "μ΅μ νμ νΌλ‘λ", "μλͺ¨ νΌλ‘λ"κ° λ΄κΈ΄ 2μ°¨μ λ°°μ΄ dungeons κ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μ μ κ° ννν μ μλ μ΅λ λμ μλ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
- kλ 1 μ΄μ 5,000 μ΄νμΈ μμ°μμ λλ€.
- dungeonsμ μΈλ‘(ν) κΈΈμ΄(μ¦, λμ μ κ°μ)λ 1 μ΄μ 8 μ΄νμ
λλ€.
- dungeonsμ κ°λ‘(μ΄) κΈΈμ΄λ 2 μ λλ€.
- dungeonsμ κ° νμ κ° λμ μ ["μ΅μ νμ νΌλ‘λ", "μλͺ¨ νΌλ‘λ"] μ λλ€.
- "μ΅μ νμ νΌλ‘λ"λ νμ "μλͺ¨ νΌλ‘λ"λ³΄λ€ ν¬κ±°λ κ°μ΅λλ€.
- "μ΅μ νμ νΌλ‘λ"μ "μλͺ¨ νΌλ‘λ"λ 1 μ΄μ 1,000 μ΄νμΈ μμ°μμ λλ€.
- μλ‘ λ€λ₯Έ λμ μ ["μ΅μ νμ νΌλ‘λ", "μλͺ¨ νΌλ‘λ"]κ° μλ‘ κ°μ μ μμ΅λλ€.
λμ κ°μκ° μ μΌλ―λ‘ κΌΌμ μμ΄ μμ νμμΌλ‘ νλ©΄ λλ€.
λλ next_permutationμ μ¬μ©νμ¬ ν΄κ²°νλ€!
λμ νμ΄
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int k, vector<vector<int>> dungeons) {
int answer = -1;
sort(dungeons.begin(), dungeons.end());
do{
int tmp = k;
int cnt = 0;
for(int i=0; i<dungeons.size(); ++i) {
if(tmp>=dungeons[i][0]){
tmp -= dungeons[i][1];
cnt++;
}
}
if(cnt>answer) answer = cnt;
} while(next_permutation(dungeons.begin(), dungeons.end()));
return answer;
}
'π μκ³ λ¦¬μ¦ > Programmers' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[C++/PGS] Lv.0 : μ°μλ μμ ν© (ꡬν) (0) | 2023.05.26 |
---|---|
[C++/PGS] Lv.2 : μ λ ₯λ§μ λλ‘ λλκΈ° (μμ νμ/bfs/dfs) (1) | 2023.05.26 |
[C++/PGS] Lv.2 : λ€λ¦¬λ₯Ό μ§λλ νΈλ (ν) (0) | 2023.04.13 |
[C++/PGS] Lv.3 : λ² μ€νΈμ¨λ² (ν΄μ / mapμ λ ¬) (0) | 2023.04.13 |
[C++/PGS] Lv.2 : μμ/μμ₯ (ν΄μ) (0) | 2023.04.13 |