💡첫번째 아이디어
이번 문제는 모든 경우의 수를 다 생각해봐야 할 것 같았다.
DFS를 이용한 모든 조합의 경우를 다 탐색해보는 알고리즘으로 구현해보았다. (구글링 참고했음,,)
일단 nCr에서 n은 문제에서 주어지고, r은 bound 변수로 반복문을 통해 1~n까지 다 DFS를 돌게 된다.
DFS 함수는 시작 인덱스인 idx와 현재까지 선택된 케이크의 개수를 나타내는 cnt가 parameter로 전달되고
cnt가 bound가 같아지면 check를 통해 선택된 수들의 역수(1/x)를 total변수에 더해주고 total이 0.99보다 크고 1.01보다 작으면 경우의 수를 나타내는 ans를 ++해준다.
DFS의 반복문은 예시를 들어보자.
n = 4, bound = 2 일때 DFS(0,0)이 실행되면
idx = 0, cnt = 0, i = 0
=> selected[0]은 false이므로 true로 바꿔주고 DFS(0,1)호출
idx = 0, cnt = 1, i = 0
=> selected[0]은 true이므로 continue
idx = 0, cnt = 1, i= 1
=> selected[1]은 false이므로 true로 바꿔주고 DFS(0,2)호출
idx = 0, cnt = 2, i = 0
=> cnt == bound이므로 check 실행후 return해서 selected[1]을 false로 바꿔주고 DFS(0,1) 계속 실행
[0] [1]
idx = 0, cnt = 1, i = 2
=> selected[2]이 false이므로 true로 바꾸고 DFS(2, 2) 호출
idx = 0, cnt = 2, i = 0
=> cnt == bound이므로 selected[2]을 false로 바꿔주고 DFS(0,1) 계속 실행
[0] [2]
idx = 0, cnt = 1, i = 3
=> selected[3]이 false이므로 true로 바꾸고 DFS(3,2)호출
idx = 0, cnt = 2, i = 0
=> cnt == bound이므로 selected[3]을 false로 바꿔주고 DFS(0,1)계속 실행
[0] [3]
....
이런 식으로 계속 하다보면 모든 조합을 체크할 수 있게 된다.
뭔가 더 좋은 방법이 있을 거 같으니 다른 사람들의 코드도 한번 읽어봐야겠다.
두번의 시도 끝에 맞췄다.
제출한 코드
#include <iostream>
using namespace std;
double cakes[20];
bool selected[20];
int bound;
double total;
int n;
int ans;
void check(){
total =0;
for(int i=0; i < n; i++){
if( selected[i]){
total = total + (1/cakes[i]);
}
}
if( total >= 0.99 && total <= 1.01) {
ans++;
}
}
void DFS(int idx, int cnt){
if(cnt == bound ){
check();
return;
}
for(int i= idx; i < n; i++ )
{
if(selected[i] ==true) continue;
selected[i] = true;
DFS(i, cnt+1);
selected[i] = false;
}
}
int main (){
cin.tie(NULL);
ios::sync_with_stdio(false);
cin >> n;
for(int i=0; i < n;i++){
cin >> cakes[i];
}
for(bound =1; bound <= n;bound++){
DFS(0, 0);
}
cout << ans ;
}
'백준 > C++' 카테고리의 다른 글
[백준/C++] 1790번 수 이어 쓰기 2 (0) | 2022.07.11 |
---|---|
[백준/C++] 16936번 나3곱2 (0) | 2022.07.10 |
[백준/C++] 15558번 점프 게임 (0) | 2022.07.07 |
[백준/C++] 25214번 크림 파스타 (0) | 2022.07.01 |
[백준/C++] 25215번 타이핑 (0) | 2022.06.29 |