[Silver IV] 반복수열 - 2331
성능 요약
메모리: 12884 KB, 시간: 112 ms
분류
구현, 수학
제출 일자
2023년 12월 10일 16:35:44
문제 설명
다음과 같이 정의된 수열이 있다.
- 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(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.
출력
첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.
풀이 방법
1. 첫번째 숫자부터 시작하여 각 자리수를 곱한 것을 리스트에 추가해줌
2. 만약 이미 방문했던 숫자가 리스트에 있다면 반복 수열이기때문에 방문했던 숫자의 인덱스를 반환
import java.util.ArrayList;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 배열의 첫번째 값
int a = sc.nextInt();
// 곱할 수
int b = sc.nextInt();
int n = solution(a, b);
System.out.println(n);
}
private static int solution(int num, int expo) {
ArrayList<Integer> list = new ArrayList<>();
// list에 num을 추가
list.add(num);
while (true) {
// 가장 최근에 넣은 값을 빼옴
int n = list.get(list.size() - 1);
// 각 자리 별로 곱한 수를 계산 할 tmp
int tmp = 0;
while (n != 0) {
// 각 자리수를 expo만큼 제곱 후 tmp에 더해줌
tmp += (int) Math.pow(n % 10, expo);
n /= 10;
}
// 만약 이미 나온 수라면? 반복수열임으로 인덱스를 찾아서 반환
if (list.contains(tmp)) {
return list.indexOf(tmp);
}
// 나오지 않은 수라면 리스트에 추가 해줌
else {
list.add(tmp);
}
}
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 14940번 : 쉬운 최단거리 Silver1(실버1) - JAVA[자바] (0) | 2023.12.12 |
---|---|
[백준] 10431번 : 줄세우기 Silver5(실버5) - JAVA[자바] (1) | 2023.12.11 |
[백준] 4963번 : 섬의 개수 Silver2(실버 2) - JAVA[자바] (0) | 2023.12.10 |
[백준] 10451번 : 순열 사이클 Silver 3(실버 3) - JAVA[자바] (1) | 2023.12.10 |
[백준] 10819번 : 차이를 최대로 Silver2(실버2) - JAVA[자바] (0) | 2023.12.01 |