문제

369 게임을 하는데 조금 이상한 규칙이 있습니다. 3, 6, 9 일 때만 박수를 쳐야합니다.
예를 들어 13, 26, 49와 같이 3, 6, 9 만으로 이루어진 숫자가 아닐 경우엔 박수를 치지 않습니다.
수현이는 게임이 진행되는 동안 참가자들이 박수를 몇 번 쳤는지 확인하고 싶습니다.
게임이 36까지 진행됐다면 참가자들이 친 박수는 총 5회입니다.

자연수 n을 입력하면 게임이 n회까지 진행되는 동안 참가자들이 친 박수의 총 횟수를 출력해주세요.

// 입력
'94'

// 출력
10

해결 방안

3, 6, 9로만 이루어져 박수를 쳐야하는 타이밍의 수를 자릿수 별로 나누고, 해당 수에서 박수를 쳤을 때 박수의 총횟수를 표로 나타내면 다음과 같다.

총박수	한자리 회차	총박수	두자리 회차	총박수	세자리 회차
1	3	4	33	13	333
2	6	5	36	14	336
3	9	...	...	15	339
		11	96	16	363
		12	99	...	...
				38	996
				39	999

예를 들어, 게임이 98회까지 진행됐을 때까지의 총 박수 횟수를 구하려면 96회까지 진행됐을 때의 총 박수 횟수를 구하면 된다.

1. 3, 6, 9로 98회차, 즉 박수를 쳐야하는 수들 중 두자리 수로만 이뤄진 배열을 만든다.
   98은 두자리 수이므로 [33, 36, 39, 63, 66, 69, 93, 96, 99]를 만든다.
2. 98보다 작은 수들 중 최댓값은 96이다. 96은 배열에서 index로는 7이고 8번째에 위치한다.
3. 여기에 한자리 회차의 총 박수 횟수(3회)를 구해서 더한 수인 11회가 정답이다.

첫째항이 a, 공비가 r인 등비수열의 첫째항부터 제n항까지의 합 Sn을 구하는 공식은 아래와 같다.

공식에 a = 3, r = 3, n = 자릿수 - 1을 대입하면 목표한 자릿수 전까지의 총 박수 횟수를 구할 수 있다.

/**
 * 게임이 turn만큼 진행되었을 때까지의 박수의 총횟수를 반환하는 함수
 * @param {number} turn 회차
 * @returns {number} 박수의 총횟수
 */
function getClapCount(turn) {
  // 회차의 자릿수
  const digits = turn.toString().length;
  // 3, 6, 9로만 이뤄진 digits의 자리수의 배열을 만든다.
  const combinations = getCombinations(["3", "6", "9"], digits);
  // 목표로 하는 회차가 3, 6, 9로만 이뤄진 수를 최초로 넘어서게 됐을 때의 index를 구한다.
  const index = combinations.findIndex((combination) => +combination >= turn);
  // index에 이전 자릿수까지 이뤄진 박수의 총횟수를 더한다.
  const clapCount = index + 1 + (3 * (Math.pow(3, digits - 1) - 1)) / 2;

  return clapCount;
}

/**
 * 주어진 배열의 값이 특정 자릿수를 차지하는 수들의 배열을 반환하는 함수
 * @param {Array<string>} array 배열
 * @param {number} digits 자릿수
 * @returns
 */
function getCombinations(array, digits = 1) {
  const combinations = [];

  if (digits === 0) return;
  if (digits === 1) return array;

  array.forEach((fixed) => {
    const subCombinations = getCombinations(array, digits - 1);
    const attached = subCombinations.map((combination) =>
      [fixed, ...combination].join("")
    );

    combinations.push(...attached);
  });

  return combinations;
}

const turn = 98;
const clapCount = getClapCount(turn);
console.log(clapCount); // 11