[백준 BOJ] 2231번 분해합 (C++/cpp)

문제 설명

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

2231번: 분해합

 

접근 방법 - 브루트포스 알고리즘을 활용한 문제

백준의 2231번 문제는 브루트포스 알고리즘을 이용하여 간단하게 해결할 수 있는 문제이다.

해당 문제는, 입력값에 대한 생성자 숫자들 중 가장 작은 숫자를 구하여 출력해야 하는 문제이다.

여기서, 자기 자신(a)과 각 자릿수들의 합이 특정 숫자(b)와 같을 시 a는 b의 생성자라 칭한다.

이 문제는 제한 시간도 넉넉하기 때문에 브루트포스 알고리즘을 이용하면 어렵지 않게 해결할 수 있다.

다만, 실행시간을 조금이나마 줄이기 위하여 필자는 탐색을 1부터가 아니라 입력값부터 시작하도록 하였다.

브루트포스 알고리즘에 대하여 어색하거나 해당 문제를 해결하는 데에 어려움이 있다면 아래 필자의 설명과 코드를 참고해보길 바란다.

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

 

코드의 실행 순서

1) 값(n)을 입력받는다.

 

2) 정답들 중 최솟값을 저장할 변수 min을 임의의 큰 수로 초기화하여 선언한다.

(필자의 경우, 입력값들 중 최댓값인 1,000,000을 min의 초기값으로 설정하였다.)

 

3) n-1부터 시작하여 아래처럼 연산하면서 값을 탐색한다.

(sum이라는 변수를 통해, 현재 탐색값이 n의 생성자인지 찾아보고자 한다.)

- sum을 현재 탐색값인 i로 초기화하여 선언한다.

- 반복문을 하나 더 실행하여, 각 자릿수를 sum에 순차적으로 더한다.

- 연산이 완료된 sum이 n과 같은지 비교한다. 만약 앞의 조건이 만족하고 min보다 더 작다면, min의 값을 현재 탐색값인 i로 변경한다.

 

4) 만약 3)에서 min의 값이 변경되지 않았다면, n에 대한 생성자가 없다는 것을 뜻한다. 이 경우에는 min의 값을 0으로 변경한다.

 

5) 최종적으로 저장된 min의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

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

//백준 2231번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;

	int min = 1000000;
	for (int i = n - 1; i >= 0; i--) {
		int sum = i;
		for (int j = 1; j < i * 10; j *= 10) {
			sum += i % (j * 10) / j;
		}
		if (sum == n && min > i) {
			min = i;
		}
	}
	if (min == 1000000) {
		min = 0;
	}
	cout << min << endl;
}

 

제출 결과

(2022.07.26 백준 2231번 문제 제출 결과)