16987 계란으로 계란치기

아... 설명 왜이래.... 문제 이해가 잘 안 됐다. 처음에 생각하기로는 계란 하나를 집고 그걸로 자기 오른쪽 계란 계속 내리치는 줄 알았는데 내리치고 다른 계란을 들어야 했다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int s[15];
int w[15];
bool dead[15];

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &s[i], &w[i]);
    }
    
    for (int i = 0; i < n - 1; i++) {
        if (dead[i])
            continue;
        
        for (int j = 0; j < n; j++) {
            if (dead[j] || i == j)
                continue;
                
            // printf("%d %d\n", i, j);
            // printf("%d %d\n", s[i], s[j]);
            
            s[i] -= w[j];
            s[j] -= w[i];
            
            if (s[i] <= 0) {
                dead[i] = true;
                break;
            }
            if (s[j] <= 0)
                dead[j] = true;
        }
    }
    
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (dead[i])
            cnt++;
    }
    
    printf("%d\n", cnt);
    
    return 0;
}

 

처음 푼 코드. 이게 완전탐색 한다고 생각하면 문제가 이해 되는데 처음 보면 뭘 원하는지 모르겠음.

 

아래는 두 번째 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int s[15];
int w[15];
int n;

int solve(int start) {
    if (start == n) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] <= 0)
                cnt++;
        }
        return cnt;
    }
    
    if (s[start] <= 0)
        return solve(start + 1);
    
    int res = 0;
    bool isBreak = false;
    for (int i = 0; i < n; i++) {
        if (start == i || s[i] <= 0)
            continue;
        
        isBreak = true;
        s[start] -= w[i];
        s[i] -= w[start];
        
        res = max(res, solve(start + 1));
        
        s[start] += w[i];
        s[i] += w[start];
    }
    
    if (!isBreak)
        return solve(start + 1);
    return res;
}


int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &s[i], &w[i]);
    }
    
    cout << solve(0) << endl;
    
    return 0;
}