[Algorithm][LeetCode 2929][Medium] Distribute Candies Among Children II

문제

두 양의 정수 n과 limit이 주어졌을 때,

세 명의 아이에게 사탕을 나누어 주는 방법의 총 수를 반환하시오. 단, 어떤 아이도 limit개를 초과해서 받을 수 없다.

예시 1:

Input: n = 5, limit = 2
Output: 3
설명: (1, 2, 2), (2, 1, 2), (2, 2, 1) 의 3가지 방법 존재

예시 2:

Input: n = 3, limit = 3
Output: 10
설명: (0,0,3), (0,1,2), (0,2,1), (0,3,0), (1,0,2), (1,1,1), (1,2,0), (2,0,1), (2,1,0), (3,0,0)

제약 사항

• 1 ≤ n ≤ 10⁶
• 1 ≤ limit ≤ 10⁶

---

풀이

1. 브루트포스 접근법

a, b의 값을 고정하면 c는 n - a - b로 자동 결정됩니다.

하지만 limit이 클 경우, 시간 복잡도는 O(limit²)으로 매우 느려집니다.

/**
 * @param {number} n
 * @param {number} limit
 * @return {number}
 */
var distributeCandies = function(n, limit) {
    let count = 0;
    for (let i = 0; i <= limit; i++) {
        for (let j = 0; j <= limit && i + j <= n; j++) {
            let k = n - i - j;
            if (k >= 0 && k <= limit) {
                count++;
            }
        }
    }
    return count;
};

2. 개선된 접근법 (시간복잡도 O(n) 또는 O(limit))

핵심 아이디어

• a + b + c = n
• 0 ≤ a, b, c ≤ limit
• ⇒ a + b = n - c 로 변환

c를 0부터 limit까지 반복하면서, a + b = n - c인 경우의 수를 계산하면 됩니다.

a + b = k일 때 가능한 (a, b)쌍의 개수는?

count = max(0, min(limit, k) - max(0, k - limit) + 1)

구현 코드

/**
 * @param {number} n
 * @param {number} limit
 * @return {number}
 */
function distributeCandies(n, limit) {
  let count = 0;

  for (let c = 0; c <= limit; c++) {
    const ab = n - c;
    const minA = Math.max(0, ab - limit);
    const maxA = Math.min(limit, ab);

    if (minA <= maxA) {
      count += (maxA - minA + 1);
    }
  }

  return count;
}

직관 정리

• (a + b + c = n) 에서 c를 고정하면 a + b = n - c
• 그 a + b에 대해 가능한 조합 수는 위 수식으로 구할 수 있음
• for문 1개로 빠르게 구할 수 있어 최적화된 방법