백준 2331. 반복수열 [성공]

1.문제 해결 전략

그래프 문제이긴 하지만 그래프로 풀지 않았다. 

 

처음에 생각했을 때 '인덱스만 잘 구하면 바로 답이 나오겠는데?'

 

라고 바로 떠올랐기 때문이다.

 

이 문제는 각 자리수 구하기 + 인덱스 찾기로 분리할 수 있다.

 

먼저, 각 자리수에 P만큼 곱하고 전부 더한 값이 다음 수열의 값이 되기 때문에

 

각 자리수를 구하는 방법을 미리 숙지해두는 것이 좋다.

 

반복이 되는 구간을 구하는건 정말 쉽게 생각할 수 있다.

 

배열에 수열의 값들이 차례차례 들어오는데

 

배열에 값이 들어올 때마다

 

방금 들어온 값은 제외하고(포함시키면 아래의 코드 조건에서 바로 만족이 돼버림)

 

완전 탐색하여 방금 들어온 값과 같은 값이 있는지 확인한다.

 

그리고 있다면 해당 인덱스를 저장하고 반복문을 탈출해주면 끝이다.

 

이 인덱스는 가장 첫번 째로 순환이 되는 값의 인덱스이다.

 

인덱스를 0부터 센다는 가정하에 이 인덱스 값이 반복순열이 시작되기 직전까지

 

배열에 존재하는 요소들의 수가 된다.

 

따라서, 인덱스가 곧 문제의 정답이 된다.

 

2.작성 코드

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector<int> v;

int main() {
	int A, P, anspoint;
	cin >> A >> P;
	bool exit = false;
	v.push_back(A);
	while (!exit) {
		int CA = A;
		int sum = 0;
		while (CA != 0) {
			int s = CA % 10;
			sum += pow(s, P);
			CA /= 10;
		}

		v.push_back(sum);
		for (int i = 0; i < v.size() - 1; i++) {
			if (v[i] == sum) {
				exit = true;
				anspoint = i;
				break;
			}
		}
		A = sum;
	}
	std::cout << anspoint << std::endl;
}

3.걸린 시간 & 느낀점

띵가띵가 유튜브보면서 15분? 걸린듯하다. 역시 풀집중을 못하겠다.

 

핵심적인 부분인 순환수열 구하는 부분은 오히려 쉽고

부가적인 부분에서 시간을 좀 뺏긴 것 같다.. 탈출 조건같은 것들..

별 것 아니었지만 한 번에 원킬원샷 할 정도도 아니었다.