문제 URL : www.acmicpc.net/problem/16938
16938번: 캠프 준비
난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다.
www.acmicpc.net
문제 접근법 : 모든경우의 수를 다 조사하면 되는 문제입니다.
시간복잡도는 2^n이 나오지만 n이 15이기 때문에
그래도 2^15 -> 3만번 정도 계산을 안하니 충분히 모든경우의수를 조사해도 괜찮습니다.
선택을 하거나 선택을 안하거나 딱 이두가지 경우만 조사해서 dfs로 해결했습니다.
또한 문제 캠프에서 사용할문제는 두 문제 이상이어야 한다라는 조건이있는데
두문제보다 작게 나온다면 그경우의수를 예외처리하는 조건도 없기때문에
테스트케이스에서 2문제이상 선택한 테스트케이스박에 없는지
2문제 이상 선택했는지에대한 조건이없어도 답이 맞더라구요 그치만 2문제 이상 선택한걸로
소스를 보여드릴게요
backtracking 안에 select를 지워도 답은 맞게 나올겁니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
//By 콩순이냉장고
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int n, l, r, x;
vector<int> v;
int total;
void backtrack(int idx = 0, int sum = 0, int select = 0, int Max = 0, int Min = 2e+9){
if (idx >= n){
if (select >= 2 && l <= sum&&sum <= r&&Max - Min >= x){//2개 이상골랐고 그합이 l이상 r이하 그리고 최대최소 차이 x이상
total++;
}
return;
}
backtrack(idx + 1, sum + v[idx], select + 1, max(Max, v[idx]), min(Min, v[idx])); //한개 고르는경우
backtrack(idx + 1, sum, select, Max, Min);//고르지않는 경우
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> l >> r >> x;
v.resize(n);
for (int i = 0; i < n; i++){
cin >> v[i];
}
backtrack();
cout << total << "\n";
}
|
cs |
궁금한점 혹은 모르는점 언제든지 댓글을 이용해주시길 바랍니다. ㅎㅎ
'백준' 카테고리의 다른 글
| 백준 1525 퍼즐 (0) | 2021.01.01 |
|---|---|
| 벡즌 1929 소수 구하기 (0) | 2021.01.01 |
| 백준 9944 NxM 보드 완주하기 (0) | 2020.12.31 |
| 백준 12931 두 배 더하기 (0) | 2020.12.31 |
| 백준 16953 A → B (2) | 2020.12.27 |
