[백준/Baekjoon] 16987 계란으로 계란치기 C++ :: Brute force & Back tracking

https://www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

---

1. Logic

조건 그대로 구현하면 된다. 구현이 약간 까다롭지만 계란의 수 N의 크기가 8로 엄청 작기 때문에 브루트포스로 풀이할 수 있다는 것을 유추할 수 있다.

 

구조체를 사용하지 않고 내구도와 무게를 따로 저장하는 배열을 선언하여 풀이했다.

---

2. Code

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int dura[10];
int weight[10];

int ans = -0x3f3f3f3f;

void solve(int egg) {
    if(egg >= n) {
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if (dura[i] <= 0) {
                cnt++;
            }
        }
        ans = max(ans, cnt);
        return;
    }
    
    bool check = false;
    for(int i = 0; i < n; i++) {
        if(egg == i) continue;
        if(dura[egg] <= 0 || dura[i] <= 0) continue;
        dura[egg] -= weight[i];
        dura[i] -= weight[egg];
        check = true;
        solve(egg+1);
        dura[egg] += weight[i];
        dura[i] += weight[egg];
    }
    if(!check) solve(egg + 1);
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> dura[i] >> weight[i];
    }
    
    solve(0);
    
    cout << ans;
}

 

 

---

 

 

3. Feedback

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90