백준) 2798 - 블랙잭 JS

📌 문제 링크

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

---

📌 문제 탐색하기

• N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

시간복잡도

• O(n^3)

알고리즘 선택

• 완전 탐색

---

📌 코드 설계하기

1. 모든 값들을 순회해서 조합하여 지금까지 누적한 큰 값이 목표값과 비교해 작거나 같은 경우 그 값을 출력
2. 모든 값을 조회해야하니 3중 for문을 사용

---

📌 시도 회차 수정 사항 (Optional)

1회차

• 이 문제는 조합으로 풀어야하는 문제여서 `let i = 0` , `let j = i + 1` , `let k = j + 1` 이 되어야 한다.
• `let i = 0` , `let j = i + 1` , `let k = i + 2` 이것도 아님!!!!   -> 이렇게 해서 틀렸다..🥲
  • `let i = 0` , `let j = i + 1` , `let k = i + 2` 가 잘못된 이유:
    1. 조합의 정의:
       • 조합은 순서를 고려하지 않고 선택하는 것이기 때문에, `i`, `j`, `k`는 항상 다른 값이어야 함
       • `j`는 항상 `i`보다 커야 하고, `k`는 항상 `j`보다 커야함. 즉, 선택된 요소들 간의 순서가 유지
    2. 올바른 인덱스 설정:
       • `let j = i + 1`: `j`는 항상 `i`보다 큰 값. 이는 `j`가 `i` 다음 인덱스부터 시작해야 한다는 것을 의미
       • `let k = j + 1`: `k`는 항상 `j`보다 큰 값. 이는 `k`가 `j` 다음 인덱스부터 시작해야 한다는 것을 의미
    3. 잘못된 설정:
       • `let k = i + 2`: 이 설정은 `k`가 항상 `i`보다 2개 큰 인덱스에서 시작하는 것을 의미. 이는 `j`와 `k`의 관계를 무시한 설정으로, 모든 가능한 조합을 정확히 탐색하지 못하게 됨
    예를 들어, `card = [1, 2, 3, 4]`일 때:
    • `let j = i + 1`, `let k = j + 1`:
      • `i = 0`, `j = 1`, `k = 2`: 조합 (1, 2, 3)
      • `i = 0`, `j = 1`, `k = 3`: 조합 (1, 2, 4)
      • `i = 0`, `j = 2`, `k = 3`: 조합 (1, 3, 4)
      • `i = 1`, `j = 2`, `k = 3`: 조합 (2, 3, 4)
    • `let k = i + 2`:
      • `i = 0`, `j = 1`, `k = 2`: 조합 (1, 2, 3) (올바름)
      • `i = 0`, `j = 2`, `k = 3`: 조합 (1, 3, 4) (잘못됨)
      • `i = 1,` `j = 2`, `k = 3`: 조합 (2, 3, 4) (올바름)
      • `i = 1`, `j = 2`, `k = 4`: (존재하지 않음)
    요약:
    • 올바른 접근: `let j = i + 1`, `let k = j + 1`는 모든 가능한 조합을 탐색하며, 각각의 인덱스가 고유한 조합을 보장
    • 잘못된 접근: `let k = i + 2`는 중복되거나 누락된 조합을 생성할 수 있어, 문제를 해결하는 데 부적합
    이 점을 고려하면, 조합 문제를 풀 때 항상 인덱스가 증가하는 방식으로 설정해야 올바른 모든 조합을 탐색할 수 있음

---

📌 정답 코드

//https://www.acmicpc.net/problem/2798
export {};

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input2.txt";
const [[n, target], card] = fs.readFileSync(filePath).toString().trim().split`
`.map((x: string) => x.split(` `).map(Number));

let max = 0;
for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    for (let k = j + 1; k < n; k++) {
      const currentNum = card[i] + card[j] + card[k];
      if (target >= currentNum && currentNum > max) max = currentNum;
    }
  }
}
console.log(max);