[바미] 블랙잭

문제

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

2798번: 블랙잭

---

코드

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [N, M] = input[0].split(" ").map((a) => Number(a)); // 첫 번째 줄에서 N과 M을 읽어옴.
const cards = input[1].split(" ").map((a) => Number(a)); // 두 번째 줄에서 카드 숫자들을 배열로 읽어옴.

let maxSum = 0; // M을 초과하지 않는 조건에서의 최대 합계를 저장할 변수.

// 가능한 모든 카드 3장 조합의 합을 계산.
for (let i = 0; i < N - 2; i++) {
    for (let j = i + 1; j < N - 1; j++) {
        for (let k = j + 1; k < N; k++) {
            let sum = cards[i] + cards[j] + cards[k]; // 선택된 3장의 카드 합계를 계산.
            if (sum > maxSum && sum <= M) { // 합계가 현재 최대값보다 크고, M을 초과하지 않는 경우
                maxSum = sum; // 최대 합계를 업데이트.
            }
        }
    }
}

console.log(maxSum); // 계산된 최대 합계를 출력.

코드설명

// 1. 입력 처리
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [N, M] = input[0].split(" ").map((a) => Number(a)); // N과 M 값을 숫자로 변환
const cards = input[1].split(" ").map((a) => Number(a)); // 카드 숫자들을 숫자 배열로 변환

이 부분에서는 파일 시스템 모듈을 사용하여 입력 데이터를 읽어온 후, 첫 번째 줄에서 N (카드의 수)과 M (목표 합)을 추출하고, 두 번째 줄에서 카드 숫자들을 배열로 변환해줍니다.

// 2. 변수 초기화
let maxSum = 0; // 조건을 만족하는 카드 3장의 합 중 최대값을 저장

maxSum 변수는 탐색 과정에서 찾은 최대 합을 저장하기 위해 사용합니다.

// 3. 카드 조합 탐색
for (let i = 0; i < N - 2; i++) {
    for (let j = i + 1; j < N - 1; j++) {
        for (let k = j + 1; k < N; k++) {
            let sum = cards[i] + cards[j] + cards[k]; // 선택된 3장의 카드 합계를 계산
            if (sum > maxSum && sum <= M) { // 합계가 현재 최대값보다 크고, M을 초과하지 않는 경우
                maxSum = sum; // 최대 합계를 업데이트
            }
        }
    }
}

여기서는 모든 가능한 카드 3장 조합을 탐색하는데 세 개의 중첩된 for 루프를 사용하여 각 카드가 서로 다르도록 조합을 생성합니다.

각 조합에 대해, 카드 3장의 합을 계산하고, 이 합이 현재까지의 최대 합보다 크면서도 M을 초과하지 않는 경우, 최대 합을 업데이트 해줍니다.

// 4. 결과 출력
console.log(maxSum); // 계산된 최대 합계를 출력

모든 조합을 탐색한 후에는 maxSum에 저장된 최대 합을 출력해줍니다. 이 때 값은 M을 넘지 않으면서도 M에 가장 가까운 카드 3장의 합이 됩니다.

문제설명

이 문제를 해결하기 위해 브루트 포스(Brute Force) 알고리즘을 사용하면 됩니다.

 

이 알고리즘은 입력으로 주어진 숫자들 중에서 3개를 선택해 그 합이 주어진 M값을 넘지 않으면서도 M에 가장 가까운 수를 찾도록 하며, 아래와 같은 단계별 접근법을 사용합니다.

1. 입력값 정의
2. 모든 조합 탐색
3. 조건 확인
4. 최적의 해결책 선택

입력값 정의 단계에선 숫자들의 배열과 M값이 주어지게 되고, 모든 조합 탐색 단계에선 주어진 숫자배열에서 가능한 모든 3개의 숫자 조합을 찾아줍니다.

그리고 조건 확인 단계에선 각 조합의 합이 M 이하인지 확인하고, 최적의 해결책 선택 단계에선 M이하의 조합 중 가장 큰 조합을 선택합니다.

 

브루트 포스 방식의 주된 장점은 그 구현의 단순성에 있습니다만, 입력 크기가 커질 수록 시간 복잡도가 기하 급수적으로 증가하는 단점이 있어 때에 맞게 사용하시는 걸 추천드립니다.