[백준/Baekjoon]<2231번> 분해합 [C/C++/Python][Class 2]

백준 2231번 분해합

 

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

---

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

---

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

---

제한

 

예제 입력 1

216

예제 출력 1

198

---

#문제 풀이 방법

1. N이 입력되고 '분해합'을 만족하는 가장 작은 생성자를 출력한다.

2. 제한 시간이 2초이다. (보통 1억번 계산하는데 1초 정도 걸린다고 간주하므로 2억번까지는 계산할 수 있을 것이다.)

3. 문제 풀 때 필요한 알고리즘을 생각하는데, 먼저 (아무생각하지말고) 가장 쉽게 브루트포스 알고리즘을 생각해보자.

4. N의 최댓값 1백만이 입력될때,

 1부터 1백만까지 모두 확인해볼 것이고

 각 자릿수를 일일이 확인할 것이므로

 최악 :(1백만)*(7자리)이므로 7백만번 계산할 것이다.

 (따라서 2억번 미만이므로 충분히 가능할 것 같다!)

 

 

반응형

 

#C/C++

#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int N;
	cin>>N;
	for(int i=1;i<N;i++)//1~N까지 모두 계산
	{
	    int sum=i;//합
	    int a=i;
	    while(a)
	    {
	        sum+=a%10;
	        a/=10;
	    }
	    if(sum==N)//분해합 맞으면
        {
            cout<<i;//최솟값 출력
            return 0;	        	        
	    }
	}
	cout<<0;//아니면 0 출력
	return 0;
}

#Python

N=int(input())
for i in range(1,N):
    Sum=i
    a=i
    while a>0:
        Sum+=a%10
        a//=10
    if Sum==N:
        print(i)
        T=False
        quit()
print(0)

 

---

※ 시간복잡도를 한번 직접 구해보자.

(머릿속으로 그려봤을 때 숫자의 자릿수가 가지는 영향력을 무시할 수 있는지 아닌지 확실하게 파악이 안되서 직접 해보려고 한다.)

#include <iostream>
using namespace std;
int main() {                            // cost         times
    ios_base::sync_with_stdio(0);      // C1            1 
    cin.tie(0);                        // C2            1
    cout.tie(0);                       // C3            1
	int N;                          // C4            1
	cin>>N;                         // C5            1
	for(int i=1;i<N;i++)            // C6            N
	{
	    int sum=i;                  // C7            N-1
	    int a=i;                    // C8            N-1
	    while(a)                    // C9            sum Ti{from i=1 to N-1}
	    {
	        sum+=a%10;              // C10           sum (Ti-1){from i=1 to N-1}
	        a/=10;                  // C11           sum (Ti-1){from i=1 to N-1}
	    }
	    if(sum==N)                  // C12           N-1(Worst),(N-1)/2 (Average)
        {
            cout<<i;                   // C13            1   
            return 0;	        	// C14            1        
	    }
	}
	cout<<0;                        // C15            1    
	return 0;                       // C16            1
}

Cn은 수행시간으로서 상수시간이 걸린다고 가정한다.

Ti는 i값의 자릿수 +1 일 것이다.

결론적으로 최악의 경우일 때,

T(N)=(C1+C2+C3+C4+C5+C13+C14+C15+C16)+C6*N+(C7+C8+C12)*(N-1)+(C9+C10+C11)*(sum Ti{from i=1 to N-1}

평균일 때,

T(N)=(C1+C2+C3+C4+C5+C13+C14+C15+C16)+C6*N+(C7+C8+C12/2)*(N-1)+(C9+C10+C11)*(sum Ti{from i=1 to N-1}

일 것이다.

따라서 가장 중요한 것은 Ti 값을 알아내는 것이다.

(위의 문제와 다르게 N값을 1,000,000에서 더 넓혀 살펴보겠다.)

(Ti-1)값

일정 구간에 따라 값이 다르지만, 상수의 값을 가진다는 것을 확인할 수 있다.

따라서 Ti=D(D는 상수)라고 하면, sum Ti{from i=1 to N-1}=D(N-1)이다.

∴시간복잡도가 O(N)임을 확인할 수 있다.