백준 알고리즘 2331번 - 반복수열

dfs를 사용해서 사이클을 찾는 문제.

계속 답을 넣어도 예제는 맞는데 답은 틀리게 나오고 반례도 도저히 못 찾겠어서 다른 블로그 보고 푼 문제.

다 맞게 풀고 MAX의 크기를 너무 크게 잡아서 에러가 뜬 것 같다(..) 로직 자체는 동일하니.. 왜 런타임 에러로 안 뜨고 그냥 "틀렸습니다"가 뜨는지...

 

처음 입력 받은 수를 A라고 하자.

규칙에 따른 수를 생성해 나가면서, 그 수를 인덱스로 가지는 배열의 값을 방문 할 때마다 1씩 늘인다.

사이클이 있다면 그 사이클을 돌텐데, 그럼 그 사이클에 해당하는 배열 값들이 늘어날 것이다.

사이클을 2번 돌리면? 사이클에 있는 수들이 전부 다 2가 되겠지. 그리고 또 사이클에 들어가면 사이클에 있는 첫 번째 값이 3이 되면서 함수를 종료시킨다. 

 

 

소스 코드

#include <iostream>
#include <cmath>
#include <cstring>

#define MAX 300001

using namespace std;

int p;
int visited[MAX]={0,};

void dfs(int num)
{
	//그 수를 인덱스로 가지는 배열의 값을 방문 할 때마다 1씩 늘린다.
	visited[num]++;
	if(visited[num]==3){
		return ;
	}
	int sum=0;
	while (num){
        //수 생성
        sum += pow((num % 10), p);
        num /= 10;
    }
	//dfs 돌리면서 계속 다음 수를 찾아나간다.	
	dfs(sum);
}

int main() 
{
	int a;
	scanf("%d%d",&a,&p);
	dfs(a);
	
	int noCycle=0;
	for(int i=0;i<MAX;i++){
//1번 돌았다면 사이클이 아니다
		if(visited[i]==1) noCycle++;
	}
	cout<<noCycle<<endl;
}

소스코드