[백준/C++] 25212번 조각 케이크

백준

 

백준 25212번 조각 케이크

---

💡첫번째 아이디어

이번 문제는 모든 경우의 수를 다 생각해봐야 할 것 같았다. 

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 ;
}