[zerobase-test]Patient Quantization

문제

질병에 걸린 환자 여러 명이 있습니다. 이 환자들을 심각도에 따라 여러 단계로 나누어 그룹 지어 관리하려고 합니다.
환자의 심각도를 나타내는 수치 p의 배열 arr가 주어지고, 환자의 심각도에 따라 나눌 단계 l이 주어질 때, 다음과 같은 규칙을 바탕으로 오차 제곱의 합 최소치를 구하는 함수, solution을 완성해주세요.

예시

• arr로 [1, 2, 3, 5, 5, 5]가 있고, l이 2라고 가정할 때, 오차 제곱의 합의 결과는 다음과 같습니다.

  	- [1, 2, 3, 5, 5, 5]를 [1, 1, 1, 5, 5, 5]로 두 단계로 나누면, 각 오차는 [0, 1, 2, 0, 0, 0]이고, 오차의 제곱은 [0, 1, 4, 0, 0, 0]이며 오차 제곱의 합은 5입니다.
  	- [1, 2, 3, 5, 5, 5]를 [2, 2, 2, 5, 5, 5]로 두 단계로 나누면, 각 오차는 [-1, 0, 1, 0, 0, 0]이고, 오차의 제곱은 [1, 0, 1, 0, 0, 0]이며 오차 제곱의 합은 2입니다.

• 이때, 오차 제곱의 합의 최소치는 2입니다.

제한사항

• l의 값은 arr의 길이보다 크지 않습니다.
• [입력 형식]
  • 환자의 심각도를 나타내는 수치 p는 1 이상 1000 이하의 정수입니다.
  • arr는 길이가 1 이상 100 이하인 배열입니다.
  • 단계 l은 1 이상 10 이하의 정수입니다.

• [출력 형식]
  • 환자의 심각도에 따라 단계를 나눴을 때, 오차 제곱의 합의 최소치를 출력합니다.

풀이1

dp에는 dp[start][level]시 오차 제곱의 합의 최소치를 저장한다.
그리고 재귀함수는 level이 1 일때 계산 가능한 함수와, level 1 로 나누는 경우의 수를 모두 구해 그 최솟 값을 저장한다.

function solution(arr, i) {
    arr.sort();

    //dp[start][n]를 start부터 시작하여, n단계로 단계를 나누었을 때 최솟값
    const dp = Array.from({ length: arr.length }, () => new Array(i + 1).fill(-1));

    return recursiveQuery(arr, 0, i, dp)
}

function recursiveQuery(arr, start, level, dp) {
    if (level === 1) return firstLevel(arr, start, arr.length - 1);

    if (dp[start][level] !== -1) return dp[start][level]
    let answer = Infinity;

    for (let end = start + 1; end < arr.length - level + 1; end++) {
      // level 1을 기준으로 나눌 수 있는 경우의 수를 모두 구하고, 그 경우의 최솟값 answer를 구한다.
        answer = Math.min(answer, firstLevel(arr, start, end - 1) + recursiveQuery(arr, end, level - 1, dp))

    }

    dp[start][level] = answer;
    return answer;
}

function firstLevel(arr, start, end) {
// level이 1일때 계산할 수 있는 함수, 평균을 기준으로 모든 값의 오차의 제곱을 구하면, 값을 구할 수 있다.
    let cnt = 0;
    let sum = 0;
    for (let i = start; i <= end; i++) {
        if (arr[i] !== 0) {
            sum += arr[i];
            cnt++;
        }
    }

    const avg = Math.round(sum / cnt);
    let ans = 0;
    for (let i = start; i <= end; i++) {
        if (arr[i] !== 0) {
            ans += Math.pow(avg - arr[i], 2);
        }
    }

    return ans;
}

그 외

dp문제를 풀 때에는 어떤 값을 dp 값에 정할지, 어떤 값을 구할 수 있고, 재귀함수로 돌릴 수 있을 지를 생각해야한다.