소프티어

이번 문제는 수학적 방법을 통해 중복 연산을 없애고, 실패 지점을 기록하는 방법으로 설계했습니다

증가된 성능들이

a b c d e 로 존재한다면

비용은 a^2 + b^2 + ...이 됩니다.

그럼 여기서 1을 증가시킨다면

(a+1)^2 + ... 이 되고, 이 식을 전개시키면

a^2 + b^2 +... +2(a+b+c+...) + 1*n 이 됩니다.

문자로 치환해보자면

(이전 비용) + 2 * (전체 성능 향상 값 합) + (성능 향상된 컴퓨터 개수)

이것을 기반으로 설계하고 코딩했습니다.

// 입력처리
const fs = require('fs')
const input = fs.readFileSync('input.txt', 'utf8')
    .trim()
    .split(/\n+/)
const [computerNum, budget] = input[0].split(' ').map(BigInt)
const clusterObj = {}
const cluster = input[1].split(' ').map(Number).sort((a, b) => a - b)
cluster.forEach(performance => {
    if (clusterObj[performance] >= 1) {
        clusterObj[performance]++
    }
    else {
        clusterObj[performance] = 1
    }
})
const clusterObjKeys = Object.keys(clusterObj)


// 목표 최소 성능
let targetPerformance = 0
// 최소 성능 비용
let cost = 0
let enhancedComputerCount = 0
let sumOfEnhancedPerformances = 0


/*
a b c d e
(a+1) b+1 c+1
a^2 + b^2 + c^2.... +2(a+b+c+d...) + n
기존 비용 합 + 2(추가된 성능 합) + 관련 컴퓨터 개수
+ 1*m (성능 향상에 추가된 컴퓨터 개수
 */
function updateCost(m) {
    // 새로운 비용
    const newCost = cost + 2 * sumOfEnhancedPerformances + enhancedComputerCount + m
    // 새로 추가된 컴퓨터 개수
    enhancedComputerCount += m
    // 선택된 컴퓨터의 성능이 1씩 추가로 증가
    sumOfEnhancedPerformances += enhancedComputerCount
    // 업데이트 된 비용이 허용 범위 이내
    if (newCost <= budget) {
        // 비용 업데이트
        cost = newCost
        // 최소 성능 올리기
        targetPerformance++
        // 성공 반환
        return true
    }
    // 비용이 초과
    else {
        // 실패 반환
        return false


    }
}




for (let i = 0; i < clusterObjKeys.length; i++) {
    // 현재 성능
    const currentPerformance = clusterObjKeys[i]
    let extraCount = clusterObj[currentPerformance]
    // 다음 성능
    const nextPerformance = clusterObjKeys[i + 1]

    // 초기 설정
    // 주어진 성능 중 제일 적은 성능에서 + 1 한 것을 최소 성능으로 목표로 초기 설정
    targetPerformance = Number(currentPerformance) + 1

    // 다음 퍼포먼스로 넘어가지않고 계속 기존 컴퓨터 성능 + 1 씩 증가
    // 배열의 마지막인 경우에는 예산 초과할때까지 반복
    while (nextPerformance === undefined || targetPerformance <= nextPerformance) {
        // 추가되는 숫자 넣기
        const isSuccess = updateCost(extraCount)
        // 예산 초과!
        if (!isSuccess) {
            console.log(targetPerformance - 1)
            return true
        }
        // 그리고 지우기
        extraCount = 0
    }
}

/*
흠..
(a + b) ^ 2 를 이용하면 방법이 있다!
(a + b) ^ 2 = a^2 + 2ab + b^2
(c + b) ^ 2 = c^2 + 2cb + b^2
두 컴퓨터에 b만큼 새로 다시 성능을 올린다면 기존 비용에서의 얼만큼?
(a^2 + c^2) 기존 비용
2b^2 + 2b(a+c)는 새로 추가되는 비용
그렇다면 성능을 추가할때, 배열이 아니라. 추가한 성능들의 함(a+c === sum)를 기록해두는게 중요
그리고 nb^2 + nb(sum)를 해주면 됨
그리고 sum은 n*b를 더해주면됨. 단순히 추가


시뮬은, 단순히 최소 성능에서 + 1 하는걸 단계적으로


let sum = 0, 기본
제일 작은 값에 + 1을 한것을 현 스탭의 최소 성능으로 설정
연산시작
+1로 최소성능에 도달하는 m개의 컴퓨터.
m
b=1 (성능 추가 증가)
sum === a + c + b * m === 0 (여기서 a,c의 개수는 기존에 성능을 늘렸던 컴퓨터들, b * m에서 m은 처음으로 성능 증가가 된 컴퓨터들의 개수, b === 1은 성능 증가 폭
money. 현재까지의 비용


기존에는 n 만큼 성능을 증가했었고, 다음 + 1(b) 최소 성능에는 m개의 추가 컴퓨터가 들어가짐
전개된 식에 의하면
기존 비용(mb^2 money^2) + 새 비용((n+m)b^2 + (n+m)(sum 전체 증가된 성능 합))
초기에는 n은 0, 연산한번되면 n=m으로 계승되고, m은 다시 배열 탐색하며 검사.

 */