백준 - 2331 반복수열

Park Inhye·2024년 3월 25일

문제

다음과 같이 정의된 수열이 있다.

D[1] = A

D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합
예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다.

입력

A 와 P
- A: D[1]
- P: 제곱수

제한 조건

1 ≤ A ≤ 9999
1 ≤ P ≤ 5

예시

// NOTE: 입력
57 2

// NOTE: 출력
4

// NOTE: 입력
153 3

// NOTE: 출력
1

해결

문제의 핵심

자릿수의 숫자가 동일하면, 이때부터 D[n]이 반복된다

ex) 5^2 + 7^2 = 7^2 + 5^2

sortJoinNum

숫자의 자릿수를 작은 순서대로 재배치하는 코드블록
D[n]의 값과 Array 안의 숫자를 비교하기 쉽게 만든다.

const sortJoinNum = (num) => {
    return +[...num.toString()].sort((a, b) => +a - +b).join('');
};

dfs

필요한 파라미터
- D[n] 처리할 숫자 num
- 제곱수 p
- D[1] ~ D[n - 1]을 저장한 배열 dArr
D[n]이 dArr에 포함된 경우
- index를 return
D[n]이 dArr에 없는 경우
- dArr에 push
- dfs 재귀
  - 숫자를 D[n]으로 설정

const dfs = (num, p, dArr) => {
    const _sum = [...num.toString()].reduce((acc, cur) => acc + Math.pow(+cur, p), 0);
    if (dArr.includes(_sum)) return dArr.indexOf(_sum);
    
    dArr.push(_sum);
    return dfs(_sum, p, dArr);
};

전체 코드

const sortJoinNum = (num) => {
    return +[...num.toString()].sort((a, b) => +a - +b).join('');
};

const dfs = (num, p, dArr) => {
    const _sum = [...num.toString()].reduce((acc, cur) => acc + Math.pow(+cur, p), 0);
    if (dArr.includes(_sum)) return dArr.indexOf(_sum);
    
    dArr.push(_sum);
    return dfs(_sum, p, dArr);
};

const solution = () => {
    const [A, P] = require('fs')
        .readFileSync('dev/stdin')
        .toString()
        .trim()
        .split(' ')
        .map(v => +v);
    
    const _dArr = [sortJoinNum(A)];
    const _index = dfs(A, P, _dArr);
    
    console.log(_index);
};

solution();