🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [head, ...inputs] = fs.readFileSync(path).toString().split('\n');
let eggs = inputs.map((it) => it.split(' ').map((it) => Number(it)));
const n = Number(head);
let answer = 0;
// idx 번째 계란을 들었다.
// 현재 깨진 계란의 개수는 cnt
const bt = (idx, cnt) => {
let flag = false;
// 만약 마지막 계란이라면 종료
if (idx === n) {
answer = Math.max(cnt, answer);
return;
}
// 만약 들고있는 계란이 깨졌다면 다음 계란 들기
if (eggs[idx][0] <= 0) {
bt(idx + 1, cnt);
}
// 만약 들고 있는 계란이 깨지지 않았다면 계란 부딪히기
else {
// 모든계란이 다 깨져서 부딪히지 못했다.
flag = false;
for (let i = 0; i < n; i++) {
// 자기 자신이거나 계란 내구도가 없으면 못치니까 continue
if (idx === i || eggs[i][0] <= 0) continue;
// 계란 치기. 한번이라도 치면 flag가 true로 작동
flag = true;
eggs[idx][0] -= eggs[i][1];
eggs[i][0] -= eggs[idx][1];
bt(idx + 1, cnt + Number(eggs[idx][0] <= 0) + Number(eggs[i][0] <= 0));
// 다음 경우의수 확인을 위한 복원
eggs[idx][0] += eggs[i][1];
eggs[i][0] += eggs[idx][1];
}
if (!flag) {
bt(idx + 1, cnt);
}
}
};
bt(0, 0);
console.log(answer);🟢 풀이
⏰ 소요한 시간 : -
ㅠㅠ 너무 어려워서 유튜브 풀이를 참고했다.. 내 풀이는 전적으로 아래 유튜브를 참고했으니.. 유튜브 설명과 동일하다.
처음엔 이게 왜 백트래킹이지 ? 무조건 브루트포스다 라고 생각했다. 왜 이게 백트래킹인줄 몰랐는데 이 개념으로 알려주시니까 알겠더라... 그리고 문제 자체가 이해하기 어려웠다. ㅠ
아무튼 bt을 계란을 든다! 의 기준으로 구현한다.
맨 처음 계란을 든다라고 생각하고 현재 들고있는 계란의 idx와 깨져있는 계란의 개수 cnt를 매개변수로 받아 bt 함수를 구현한다. 당연히 시작은 bt(0, 0).
내가 들고 있는 계란이 마지막 계란이라면 계란치기 행위를 종료해야 하니 return 해준다. 코드를 보면 flag니 answer니 있는데 일단은 다음으로 넘어가준다.
그리고 이제 현재 들고 있는 계란의 내구도가 0보다 작다면 계란을 부딪히지 못하기 때문에 다음 계란을 들어준다. => bt(idx+1, 0)
만약 들고있는 계란으로 다른 계란을 칠 수 있으면 모든 경우의 수를 백트래킹 방식으로 돌아주는데 이 부분 때문에 풀이를 보고도 구현이 힘들었다. 여기서 말하는 백트래킹 방식은 함수를 재귀적으로 다시 호출해준다가 아닌, 반복문으로 확인해준다는 뜻이다.
현재 1번 계란을 들고있으면 이 계란은 이론상 n개의 모든 계란을 부딪힐 수 있기 때문에 for문 을 n번만큼 돌아주고 만약 자기자신과 부딪히려고 하거나, 내가 치려고 하는 계란이 깨졌다면 continue로 다음 계란을 확인하면 된다. 부딪힐 수 있다면 계란을 부딪혀 준다.
eggs[idx][0] -= eggs[i][1];
eggs[i][0] -= eggs[idx][1];이렇게 계란을 한 번 부딪힌다면 바로 계란을 내려놓고 다음 계란으로 가야하기 때문에 다음 계란을 드는 백트래킹 재귀함수를 수행해주면 된다.
다음 계란이기 때문에 idx번호 증가해주고 내가 현재들고 있던 계란과 부딪힘을 당한 계란의 깨짐 여부에 따라 cnt 개수를 조절해서 bt를 재귀호출 해주면된다.
이렇게 돌다보면 마지막 idx에 도달하고 윗부분에서 설명한 조건문으로 들어가게 되는데 이때 내가 지금껏 세었던 cnt와 전역 변수의 answer 중에 최대값으로 answer를 갱신해주면 된다.
이러고 return을 하게되면 재귀호출이 끝나는것이 아니라 재귀호출이 끝난 단계 즉 이전단계로 돌아오는데 이 단계에서 아까 우리가 감소해줬던 내구도를 원상 복구해준다.
eggs[idx][0] += eggs[i][1];
eggs[i][0] += eggs[idx][1];이 과정을 다 수행해주면 자동으로 최대값이 갱신되어 있을 테니 answer를 출력해주면 되는데 하나의 계란을 들었을 때 즉 한 번의 bt를 수행할 때 계란을 부딪히지 못하는 경우가 생긴다. 문제에서 이런경우 다음 계란을 들으라고 명시하고 있으니 다음 백트래킹을 수행해주면 된다. 이 조건을 확인하기 위해 flag 변수를 관리해주는 것이다.
🔵 Ref
