[알고리즘] 가지를 치지 않는다면, 시간은 당신을 칠 것입니다.

이 가지 아닙니다.

 

일단 문제 링크입니다.
https://www.acmicpc.net/problem/28075

필자는 "시간 초과" 라는 글자를 보면 손이 떨립니다.

내가 어떻게 풀었는데...

 

한 줄 한 줄 코드를 써 내려가며 스스로에게 말하죠.
“괜찮아. 현대 컴퓨터는 빠르니까.”

그렇게 자신을 속이며 제출 버튼을 누른 그 순간—

[시간 초과]

…잠시 정적이 흐르고,

시간초과는 저에게 말을겁니다.
“너 진짜 탐색 다 돌릴 생각이었어?” 

---

💥 완전탐색은 당신을 배려하지 않는다.

문제의 조건은 이랬습니다:

• 총 N일 동안 일을 합니다.
• 매일 2개의 업무(task) 중 하나를 선택하고, 그 업무는 3개의 장소(place) 중 하나에서 수행됩니다.
• 같은 장소에서 연속으로 일하면 점수가 절반이 됩니다.
• M점 이상을 달성하는 모든 가능한 경우의 수를 구해야 합니다.

이걸 어떻게 풀까?
자연스럽게 DFS + 완전탐색을 떠올렸습니다.

업무 2개, 장소 3개. 하루당 6가지 선택지.
즉, 총 경우의 수는 6^N.

 

사실 이건 시간초과가 나지않는 수준입니다. 

 

하지만 문신처럼 박힌 저희 뇌는 아 이거.. 가지쳐야해.. 라고 떠오르게해주고 가지를 칩니다.

"가망없는 시도는 하지않는다 라는 비장함과 함께"

---

🔪 가지치기 전략 요약

1. 희망고문 차단: 아무리 잘해도 점수 못 넘긴다면 → 바로 종료
2. 목표 이미 달성: 남은 선택 다 유효하니 경우의 수 계산해서 바로 리턴
3. 장소 반복 감점: 전날과 같은 장소면 점수 절반

---

✨ 풀이 코드

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

console.log(input);

const [N, M] = input[0].split(" ").map(Number);

//일하는 배열만듬
const work = input.slice(1).map((line) => line.trim().split(" ").map(Number));

//업무에서 받을수있는 최댓값
const maxSingle = Math.max(...work.flat());

//남은날에 대해 이론상 최댓값(같은곳 방문했을떄 /2 되는거)을 설정해줍니다.
//남은날이 3일인데 이론상 최댓값을 더해도 안되는거면 불가능한것.
const maxScore = Array(N).fill(0);
maxScore[N - 1] = maxSingle;

for (let i = N - 2; i >= 0; i--) {
  maxScore[i] = maxScore[i + 1] + maxSingle;
}
console.log("maxscore = ", maxScore);

function dfs(day, currentScore, prevPlace) {
  if (day === N) return currentScore >= M ? 1 : 0;
  if (currentScore + maxScore[day] < M) return 0;
  if (currentScore >= M) return 6 ** (N - day);

  let cnt = 0;
  for (let task = 0; task < 2; task++) {
    for (let place = 0; place < 3; place++) {
      let point = work[task][place];
      if (place === prevPlace) point = Math.floor(point / 2);
      cnt += dfs(day + 1, currentScore + point, place);
    }
  }
  return cnt;
}

console.log(dfs(0, 0, -1));

---

📈 maxScore 배열로 희망을 계산하다

DFS에서 "남은 날 동안 최대로 벌 수 있는 점수"를 미리 계산해서,
그 이상이 되지 않으면 아예 탐색하지 않는 방식을 썼습니다.

const maxScore = Array(N).fill(0);
maxScore[N - 1] = maxSingle;

for (let i = N - 2; i >= 0; i--) {
  maxScore[i] = maxScore[i + 1] + maxSingle * 2;
}

여기서 maxSingle은 업무 중 받을 수 있는 가장 큰 점수고,
매일 두 번 반복해서 받을 수 있다고 가정합니다.
말하자면… 최대치 희망고문 시뮬레이션이죠.

이 덕분에 DFS는 비효율적인 경로를 미리 차단하고,
필요한 경로만 똑똑하게 탐색하게 됩니다.

---

습관적으로 가지를 치자

“DFS는 탐색의 정석이지만,
조건 기반 가지치기 없이 쓰면 순수한 폭탄이다.”

 

혹시 지금 여러분이
“이 정도면 되지 않을까?”
라고 생각하고 있다면,
한 번쯤 자신에게 질문해보세요.

“이 경로, 진짜로 볼 가치가 있나?”

 

그리고 그 가지가 불필요하다면 과감히 쳐버리세요.
그 한 줄이 당신을 시간의 압박에서 살릴 수도 있습니다.

---

필자처럼 손 떠는 분들이 더는 생기지 않길 바라며,
이만 가지치기 된 글을 마칩니다.