[JavaScript/백트래킹] 백준 골드 5 : 16987 - 계란으로 계란치기

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

16987번: 계란으로 계란치기

---

📌 작성한 코드 

// 16987
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
let s = [];
let w = [];

input.forEach((str) => {
    const [a, b] = str.split(" ").map(Number);
    s.push(a);
    w.push(b);
});

let answer = 0;

const backTracking = (at) => {
    if (at === N) {
        const temp = s.filter((val) => val <= 0).length;
        if (temp > answer) answer = temp;
        return;
    }

    let flag = false;
    for (let i = 0; i < N; i++) {
        if (at === i || s[i] <= 0 || s[at] <= 0) continue;

        s[at] -= w[i];
        s[i] -= w[at];

        flag = true;
        backTracking(at + 1);
        s[at] += w[i];
        s[i] += w[at];
    }
    if (!flag) backTracking(at + 1);
};

backTracking(0);
console.log(answer);

📌 풀이 

계란의 내구도와 무게가 주어졌을 떄 최대 몇개의 계란을 깰 수 있는지 구하는 문제이다. -> 백트래킹으로 풀 수 있다.

 

계란을 깰 때는 몇가지 규칙이 있는데 이를 주의하면서 문제를 풀어야 한다.

(1) 가장 왼쪽 계란을 들어서 다른 계란을 내리치고, 다음 계란(오른쪽에 있는 계란)을 들어야 한다.

(2) 내리칠 수 있는 계란은 든 계란의 오른쪽에 있는 계란이 아니라 깨지지 않은 계란이다. (주의)

(3) 꺨 수 있는 계란이 없거나 현재 들고있는 계란이 깨졌으면 내리치지 않고 다음 계란으로 넘어간다.

 

 

종료 조건 : 현재 들고있는 계란이 N일 때 

- 가장 왼쪽의 계란을 들고 내리치고, 오른쪽으로 넘어가니까 현재 든 계란이 N이 되면 종료한다. (0~N-1까지의 계란 존재)

- 그리고 현재 상태에서 깨진 계란의 수를 세서 가장 큰 수면 저장한다. 

if (at === N) {
        const temp = s.filter((val) => val <= 0).length;
        if (temp > answer) answer = temp;
        return;
    }

백트래킹 : 존재하는 계란을 모두 확인하면서 내리칠 수 있는지 확인하고, 가능하면 내리치기 

- 내리치면 두 계란 모두 상대 계란의 무게만큼 내구도가 줄어든다.

- 내리친 다음에 위치를 오른쪽으로 이동시켜서 재귀를 반복한다,

- 모든 계란을 확인했는데 깰 수 있는 계란이 없었으면 다음 위치로 넘어가서 재귀를 반복한다. 

let flag = false;
for (let i = 0; i < N; i++) { // 모든 계란 확인하기
    if (at === i || s[i] <= 0 || s[at] <= 0) continue; // 꺠진 상태인지 아닌지, 들고 있는 계란과 같은 계란인지 확인하기

    s[at] -= w[i]; // 양쪽 계란의 내구도 줄이기
    s[i] -= w[at];

    flag = true;
    backTracking(at + 1);
    s[at] += w[i];
    s[i] += w[at];
}
if (!flag) backTracking(at + 1); // 모든 계란 확인했는데 깨진게 없을 시 다음으로 넘어가기

✅ 성공