⭐️ 문제

백준 - 14929번 문제 바로 가기

⭐️ 풀이

❓ 시간 복잡도를 고려하지 않았다면 간단한 문제지만 , N <= 100,000 이란 점을 고려하면 고민을 해봐야 할 문제입니다.
반복문 중첩을 사용하지 않기 위해 , Σ의 모든 과정을 손으로 써보고
a1(b2+b3+...+bn)+a2(b3+b4+...+bn)+....an-1(bn) 로 요약이 됐습니다.
아래 코드는 이를 구현한 것입니다.

function solution(input) {
    // 연산을 진행할 횟수
    const n = input[0][0];
    // 연산 대상
    const inputArr = input[1];
    // 합 저장 배열 , 역순부터 저장
    const b = [];

    let sum = 0;
    let j = 0;

    for (let i = inputArr.length - 1; i > 0; i--) {
        if (b.length !== 0) {
            b.push(b[j] + inputArr[i]);
            j++;
        } else {
            b.push(inputArr[i]);
        }
    }
    let t = b.length - 1;
    for (let i = 0; i < inputArr.length - 1; i++) {
        sum += inputArr[i] * b[t];
        t--;
    }
    console.log(sum);
}

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
    input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
    solution(input);
    process.exit();
});

✅ bn부터 역순으로 bn-1을 더하고 , bn-1을 더한 값에 bn-2를 더하는 것을 반복하여 b1까지 더한 배열을 만들어줍니다.

 for (let i = inputArr.length - 1; i > 0; i--) {
        if (b.length !== 0) {
            b.push(b[j] + inputArr[i]);
            j++;
        } else {
            b.push(inputArr[i]);
        }
    }

✅ 이후 , a1 과 배열 b의 맨 뒤 값 (b2+b3+...bn)을 곱해주고 , 마지막에 an-1과 bn이 곱해진 값이 만들어지도록 하였습니다.

let t = b.length - 1;
    for (let i = 0; i < inputArr.length - 1; i++) {
        sum += inputArr[i] * b[t];
        t--;
    }

해당 코드는 O(n)의 시간 복잡도를 가지게 됩니다.

도움이 되셨으면 좋겠습니다 ! 감사합니다.
(틀린 점 및 개선 방안 댓글로 알려주시면 감사하겠습니다.)