[JavaScript/Greedy] 백준 골드 4 : 1744 - 수 묶기

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

1744번: 수 묶기

---

📌 작성한 코드 

// 1744
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());
const list = input.map(Number).sort((a, b) => a - b);

const solution = () => {
    if (N === 1) {
        console.log(list[0]);
        return;
    }

    let sum = 0;
    for (let i = 0; i < N; i += 2) {
        const first = list[i];
        const second = list[i + 1];

        if (first > 0) break;
        if (second === undefined) {
            sum += first;
            break;
        }
        if (first < 0 && second > 0) {
            sum += first;
            break;
        }

        sum += first * second;
    }

    for (let i = N - 1; i >= 0; i -= 2) {
        const first = list[i];
        const second = list[i - 1];

        if (first <= 0) break;
        if (second === undefined) {
            sum += first;
            break;
        }
        if (first > 0 && second <= 0) {
            sum += first;
            break;
        }

        if (first !== 1 && second !== 1) {
            sum += first * second;
        } else {
            sum += first + second;
        }
    }

    console.log(sum);
};

solution();

 

📌 설명 

수열을 적절히 묶어서 수열의 합이 최대가 나오게 하는 알고리즘을 구하는 문제이다. 

 

💡 수열 묶기의 조건

(1) 각 숫자들은 한 번 만 묶이거나, 아예 묶이지 않는 상태로 존재할 수 있다.

- {1,2,3}일 때 (1,2), 3 ->  1,2는 한번씩 묶이고, 3은 묶이지 않는다.

- {1,2,3}일 때 ((1,2),3) -> 두번 묶이는 것 불가능! 각 숫자는 한 번 만 묶일 수 있다.

(2) 묶인 수는 서로 곱한다.

 

💡 최대의 값을 구하기 위한 방법

(1) 양수는 가장 큰 수와 그 다음으로 큰 수를 곱하는 것이 가장 큰 수를 만들 수 있는 방법이다. (큰 수끼리 곱해야 더 큰 수가 나오기 때문)

(2) 음수도 존재하는데 음수는 작은 수 끼리 곱하는 것이 큰 수를 만들 수 있는 방법이다. (-90 * -80 이렇게 큰 수끼리 곱하면 양수의 큰수가 나오기 때문) 

 

💡 주의해야 할 점 

- N이 1이면 수열의 값이 답이다.

- 음수끼리 묶는 경우에 0이 나오면 0을 곱하는 것이 더 큰 수를 만들 수 있는 방법이다.(음수 * 0 = 0, 음수를 더하는 것보다 더 큰 값) 

- 양수끼리 묶는 경우에 1이 나오면 1은 더하는 것이 더 큰 수를 만들 수 있는 방법이다.(1 * 1 = 1, 1 + 1 = 2) 

---

(1) 양수끼리의 합 구하기 

for (let i = N - 1; i >= 0; i -= 2) { // 2개씩 줄여 나가기
    const first = list[i]; // 큰 수 
    const second = list[i - 1]; // 그 다음으로 큰 수 

	// 탐색하고자 하는 다음 수(first)가 음수이면 더이상 확인할 필요 없음
    // first가 존재하지 않는 경우는 인덱스 i에서 선택될 일이 없음
    if (first <= 0) break; 
    
    // first는 있는데, second는 없는 경우에는 짝이 맞지 않기 때문에 first를 더하고 탈출
    if (second === undefined) { 
        sum += first;
        break;
    }
    
    // 둘 다 존재하지만, 한쪽은 음수고 한쪽은 양수인 경우에 위와 마찬가지로 양수인 first만 더하고 탈출
    if (first > 0 && second <= 0) {
        sum += first;
        break;
    }

	// 1이 나온 경우 둘을 곱하는 것보다 더하는 것이 더 큰 값을 얻을 수 있음
    if (first !== 1 && second !== 1) {
        sum += first * second;
    } else {
        sum += first + second;
    }
}

 

(2) 음수끼리의 합 구하기 

for (let i = 0; i < N; i += 2) {
    const first = list[i];
    const second = list[i + 1];

	// first가 양수면 탈출
    if (first > 0) break;
    
    // first는 존재하지만 second는 존재하지 않을 때 first만 더하고 탈출
    if (second === undefined) {
        sum += first;
        break;
    }
    
    // 둘 다 존재하지만 한쪽이 양수인 경우에도 first만 더하고 탈출
    if (first < 0 && second > 0) {
        sum += first;
        break;
    }

	// 둘 중 하나가 0인 경우도 곱하는 것이 낫기 때문에 경계를 0 포함해서 사용
    sum += first * second;
}

 

✅ 성공