[C++] 백준 16987번: 계란으로 계란치기

🔗 문제

16987번: 계란으로 계란치기

16987번: 계란으로 계란치기

 

🖍 풀이

 

문제 정리

내구도와 무게를 가진 계란 N개가 있다.

왼쪽부터 깨지지 않은 계란을 집어들고 다른 안 깨진 계란을 깰 시도를 한다.

이 때! 내가 깨질 수도 있고 다른 계란이 깨질 수도 있다.

• 두 계란의 내구도는 상대 계란의 무게만큼 감소한다.
• 내구도가 음수가 되면 그 계란이 깨진다.

이걸 깰 계란이 없을 때까지 반복한다.

 

깰 수 있는 계란이 여러 개 있을 때 탐욕 기법을 이용해서 풀어야 하나 고민을 했지만! 어떤 계란을 깨는지에 따라 다음 계란이 깰 수 있는 대상이 달라지기때문에 DFS를 이용한 완전 탐색으로 풀어주었다.

 

 

💾  소스

#include <iostream>

int N, answer = 0;
bool crack[20] = {false, };
int S[20]; int W[20];

bool flag = false;
void DFS(int pick, int sum)
{
    answer = (answer > sum ? answer : sum); // 지금까지 깬 최대 계란 수 확인
    
    // 내가 들고 있는 계란이 깨진거라면 다음 계란 들자.
    for(; pick<N; ++pick)
    {
        if(crack[pick] == false)
            break;
    }
    
    if(pick >= N)
    {
        return;
    }
    
    for(int i=0; i<N; ++i)
    {
        if(i == pick || crack[i]) continue;
        
        S[i] -= W[pick];
        S[pick] -= W[i];
        
        if(S[i] <= 0) crack[i] = true;
        if(S[pick] <= 0) crack[pick] = true;
        
        DFS(pick+1, sum + crack[pick] + crack[i]);
        
        S[i] += W[pick];
        S[pick] += W[i];
        
        if(S[i] > 0) crack[i] = false;
        if(S[pick] > 0) crack[pick] = false;
    }
}

int main()
{
    
    std::cin >> N;
    for(int i=0; i<N; ++i)
    {
        std::cin >> S[i] >> W[i];
    }
    
    DFS(0, 0);
    
    std::cout << answer;
    return 0;
}