[백준 BOJ] 4673번 셀프 넘버 (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

 

접근 방법 - 브루트포스 알고리즘에 대한 응용문제

백준의 4673번 문제는 브루트포스 알고리즘을 활용하여 해결해야 하는 연산 문제이다.

해당 문제는, 문제에서 정의하는 셀프 넘버를 특정 범위 내에서 모두 출력해야 하는 문제이다.

필자의 경우엔, 셀프 넘버를 구하는 함수를 따로 구현하여 이를 실행한 뒤 모두 출력을 하도록 하였다.

bool형 배열을 활용하기도 하였는데, 어떻게 활용하였는지에 대한 설명은 아래에 이어 설명하고자 한다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 셀프 넘버인지에 대한 여부를 저장할 bool형 배열(t)을 전역 변수로 선언한다. (0: 셀프 넘버O / 1: 셀프 넘버X)

 

2) 반복문을 실행하여 셀프 넘버를 판별하는 함수를 순차적으로 수행한다. (아래는 함수 내용)

- 탐색하는 숫자(n)를 임의의 변수 num에 저장한다.

- n의 각 자릿수를 num에 차례로 더한다.

- num이 문제에서 제시된 범위인 10000 이하 안에 있는 숫자라면, 이를 배열 번호로 갖는 t의 배열값에 1을 더한다.

- 1을 반환한 뒤 해당 함수를 종료한다.

 

3) 판별이 끝났다면, 다른 반복문을 실행하여 출력을 실행한다.

만일 현재 탐색값(i)을 배열 번호로 갖는 t의 배열값이 0이라면, 이는 셀프 넘버이다. 따라서 이 경우엔, 해당 탐색값을 출력한다.

 

4) 셀프 넘버를 모두 출력하였다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 4673번 코드
bool t[10001];
int self_num(int n) {
	int num = n;
	for (int i = 1; i < 10000; i *= 10) {
		num += n % (i * 10) / i;
	}
	if (num < 10000) {
		t[num]++;
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	for (int i = 1; i < 10000; i++) {
		self_num(i);
	}
	for (int i = 1; i < 10000; i++) {
		if (t[i] == 0) {
			cout << i << endl;
		}
	}
}

 

제출 결과

(2022.03.26 백준 4673번 문제 제출 결과)

bool형 배열은 생각보다 아직 어색해서 여러 고난을 겪었다고 하더라