4673_셀프 넘버 (C++)

4673번: 셀프 넘버

#include <iostream>
using namespace std;

int visited[10001] = { 0, }; //방문 확인

void dfs(int num) {
	int temp = num;

	while (num) {
		int n = num % 10;
		temp += n;
		num /= 10;
	}

	if (temp<=10000 && !visited[temp]) {
		visited[temp] = 1;
		dfs(temp);
	}
	else return;
}

int main() {
	int num = 1;
	
	for (int i = 1; i <= 10000; i++) {
		if (!visited[i]) {
			dfs(i);
		}
	}

	for (int i = 1; i <= 10000; i++) {
		if (!visited[i])
			cout << i << '\n';
	}
}

 

[문제 풀이 생각 과정]

1. 셀프 넘버가 처음에 이해가 잘안되서 좀 생각했다.

  예) 셀프 넘버 31 == 31의 생성자가 없다 == d(n)=31인 n이 없다 로 이해완료됨!

2. 셀프 넘버 수 <<< 생성자 존재하는 숫자 수 여서 '셀프 넘버를 바로 구하는 방법'을 생각했으나 실패

3. 1~10000 생성자 존재하는 수 제외하고 나머지 출력하는 방식으로 생각

  문제에서 d(d(d(n))) 와같이 힌트를 줬다. -- 이 부분보고 dfs 떠올랐고 습관적으로 visited[] 만들었다 ^..^

4. 하지만 런타임 에러 났다.

  d(n)을 돌리기 위한 변수 temp가 10000이 넘는 경우를 생각하지 않아서 - visited[] 범위를 초과한상태로 돌린 것!

  temp 범위 체크해서 다시 돌렸더니 통과!

 

그래도 dfs는 몇 문제 풀어봤다고 생각해낸 나.. 칭찬해 ㅠㅠ

** 배열사용할때는 무조건! 범위 체크하자!! 런타임 에러 그으만