[백트래킹] C11 백준 16987 계란으로 계란치기 풀이

문제

• 16987

풀이 과정

• 최대 몇 개의 계란을 깰 수 있는지가 출력값이므로 모든 경우의 수를 확인해야 함
• 내구도(s), 무게(w)가 주어졌을 때
  • 왼쪽에서부터 달걀을 쥐고 끝까지 확인하는 조건 필요
    • 쥔 달걀과 아닌 달걀을 비교해야 하므로 (나) 제외 조건 추가
  • 달걀을 쥐고 내려쳤을 경우
    • 깨진 달걀(값이 0)인 경우 넘어가는 조건 추가
    • 쥔 달걀로 깰 수 있는 달걀이 없을 때의 조건 추가
    • 쥔 달걀과 아닌 달걀의 각각의 무게가 서로의 내구도를 깎는 조건 추가
• 헬창은 이렇게 무섭다

#include <stdio.h>

#define MAX 9

typedef struct egg{
    int s;
    int w;
} egg;

int n;
egg eggs[MAX];
int result;

void func(int num) {
    if (num == n) {
        int broken = 0;
        for (int i=0; i<n; i++) {
            if (eggs[i].s <= 0) broken++;
        }
        if (broken > result) {
            result = broken;
        }
        return;
    }
    
    if (eggs[num].s <= 0) {
        func(num+1);
        return;
    }
    
    int check = 0;
    for (int i=0; i<n; i++) {
        if (num != i && eggs[i].s > 0) {
            check = 1;
            
            eggs[num].s -= eggs[i].w;
            eggs[i].s -= eggs[num].w;
            func(num+1);
            eggs[num].s += eggs[i].w;
            eggs[i].s += eggs[num].w;
        }
    }
    if (check == 0) {
        func(num+1);
    }
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d %d", &eggs[i].s, &eggs[i].w);
    }
    func(0);
    
    printf("%d", result);
    
    return 0;
}