1. 문제 분석
어떤 수 M과 M의 각 자릿수를 합한 값을 분해합이라고 한다.
어떤 수 N의 분해합이 M일 때 M을 N의 생성자라고 한다.
N의 생성자의 최솟값을 구해라.
입력값의 범위는 1부터 1,000,000까지이다.
2. 자료 구조 분석
입력값을 받는 변수 boon_hae_hap과
정답 값을 받는 변수 answer 외에 자료구조는 쓰지 않았다.
3. 알고리즘 설명
1.세자릿수의 생성자를 구할 경우
2.분해합 = (100+1)(100의 자리 숫자)+(10+1)(10의 자리 숫자)+(1+1)(1의 자리 숫자)
3.n의 자릿수의 생성자를 구할 경우
분해합=(10^n+1)(10^n의 자리 숫자)+(10^(n-1)+1)(10^(n-1)의 자리 숫자)+…+(1+1)(1의 자리 숫자)
4.각 자리 숫자는 0~9이므로
5.n개의 for문 만큼 0~9까지 돌면 된다.
입력 값의 범위는 1에서 100만 사이이다.
분해합은 무조건 자기 자신보다 작을 수밖에 없다.
자연수는 1 이상이기 때문이다.
입력값이 1,000,000인 경우도 100만보다 작으므로
문제 풀이에서는
첫째 자리부터 여섯번째 자리까지의 값을 구할 것이다.
4. 코드
#include <iostream>
using namespace std;
int main(){
int boon_hae_hap;
cin>>boon_hae_hap;
int answer=1000000;
for(int a=0;a<=9;a++){
for(int b=0;b<=9;b++){
for(int c=0;c<=9;c++){
for(int i=0;i<=9;i++){
for(int j=0;j<=9;j++){
for(int k=0;k<=9;k++){
int candidate=100001*a+10001*b+1001*c+101*i+11*j+2*k;
if(candidate==boon_hae_hap&&candidate<answer)
answer=100000*a+10000*b+1000*c+100*i+10*j+k;
}
}
}
}
}
}
if(answer==1000000)
answer=0;
cout<<answer<<endl;
}5. 분석
문제풀이에 사용된 알고리즘은 Brute-force 알고리즘이다.
이렇게 구해도 되나 싶을 정도로 for문을 많이 썼는데
문제는 통과하였다.
공간 복잡도는 간단하다. 자료구조를 사용하지 않고
변수만 사용하였으므로 O(1)일 것이다.
시간 복잡도는 오히려 내가 생각한 것이 틀린 것 같다.
처음에는 O(N^6)이라고 생각했었는데(for문이 6개니까)
내가 구하려는 숫자가 N일 경우 1~N-1까지의 값들을 찾는 것이므로
결국 시간 복잡도를 따져보면 for문이 많은데도
O(N) 이라는 결과가 나온다.
세자리일경우 101010이니까 1000번.
내가 사용한 Brute force 알고리즘이
이 문제를 해결할 때 그렇게 나쁜 방법은 아닌 것 같다.
- 센티넬에 대한 이야기
if(answer==1000000)
answer=0;
이 부분이 있는데, 처음 answer를 100만으로 정한 이유는
최대 생성자 값이 100만보다 크거나 같을 수 없기 때문에
sentinel로 정해 놓았고,
만약에 이 값이 바뀌지 않았으면 생성자를 찾지 못했다는 뜻이기 때문에
문제의 조건을 맞추기 위해 이 때 answer값을 0으로 바꾸었다.
더 좋은 방법이 있는지 찾아봐야겠다.
