백준 2331 반복수열

www.acmicpc.net/problem/2331

2331번: 반복수열

배열하나 잡고 dfs돌리면서 방문처리 해주면 되는 쉬운 문제인줄 알았으나 5연속 연타임 에러를 맞고 

다시 꼼꼼히 살펴봤다.

일단 배열의 크기는 아무리 커도 9^5 * 5 이니 30만을 넘지 않는다.

 

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

int vis[300000];
int a, p, ans;

int cal(int n) {
	int ret = 0;
	while (n > 0) {
		ret += (int)pow(n % 10, p);
		n /= 10;
	}
	return ret;
}

void dfs(int cur, int cnt) {
	if (vis[cur] > 0) {
		ans = vis[cur] - 1; return;
	}
	vis[cur] = cnt;
	//printf("cal(%d) = %d, cnt= %d\n", cur, cal(cur), cnt);
	dfs(cal(cur), cnt + 1);
}

int main() {
	cin >> a >> p;
	dfs(a, 1);

	cout << ans << endl;

	return 0;
}

 

각 숫자를 인덱스로 해서 체크해주고 계속 재귀를 돌다가 이미 방문했던 적이 있으면 종료해준다.

처음에는 dfs를 int 형으로 해줬는데

	if (vis[cur] > 0) {
		ans = vis[cur] - 1; return;
	}

이 조건문 밑의 코드들이 되는 리턴값이 없어서 런타임 에러가 발생한것 같다. 그래서 ans에 넣어주고 return; 해줬다.

 

내가 문제를 풀면서 런타임 에러를 여럿 경험해봤는데 정말 대부분은 인자의 반환값이 잘못된다거나, 배열의 크기를 잘못 설정해줬다거나 루프를 빠져나오지 못하거나 int형 범위를 초과하거나 등 몇가지 경우의 수밖에 되지 않으니 주변 부분을 잘 살펴봐야 한다.

 

www.acmicpc.net/board/view/22980

글 읽기 - 주로 런타임 에러가 발생하는 이유는 무엇인가요?

이 글이 참고가 많이 되었다.