[백준문제풀이] 2331 반복수열

 

풀이일시 : 2020-10-13

​

 

문제 :

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

D[1] = A

D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=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)가 주어진다.

ex)

57 2

​

 

출력 :

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

ex)

4

​

 

풀이 :

반복수열이 되는 가운데 반복이 아닌 수들만 추출하면 될 것이다. 수가 나오면 visit배열을 ++ 해준다. 두번째 나왔을때 visit배열이 ++가 될것이고 dfs를 return 시켜준다. 그랬을 때 결과는

visit

1

2

1

2

2

1

2

1

2

2

2

2

2

2

이와같이 생성될 수 있을 것이다. 그러면 무한으로 반복하지 않게 할 수 있고 visit에서 1인 부분만 반복이 되지 않은 부분으로 판단할 수 있다.

 

dbstndi6316.tistory.com/64

[기본문제풀이] DFS 깊이우선탐색

#include <iostream>
#include <cmath>
using namespace std;

//floor를 이용한 반올림함수 : floor에 0.5를 더해주면 반올림이된다.
int result=0;
int visit[1000000];

int mult(int A, int P) {
	int next = 0;
	while (A > 0) {
		next = (int)floor(pow(A % 10, P) + 0.5) + next;
		A /= 10; //A의 모든자리수를 해줘야되기때문이다.
		// 9876였다면 9876%10 = 6 -> /10 = 987 -> 987%10 = 7 이런식으로 하나씩 감해간다
	}
	return next;
}
void dfs(int A, int P) {
	visit[A]++; // true로 두면 계속 1일테니..
	if (visit[A] > 2) {
		return;
	}
	dfs(mult(A, P), P);
}

int ma
	int A, P;
	cin >> A >> P;
	dfs(A, P);

	for (int i = 0; i < 1000000; i++) { //1000000까지 반복해서 구해준다.
		if (visit[i] == 1) { //딱한번만 나온걸 result+해줘야됨
			result++; 
		}
	}
	cout << result;
}

 

참고자료 : 수식함수

dbstndi6316.tistory.com/32

[개념정리] C++ 수식함수들