[Baekjoon] 2231번 분해합 (C++, Python)

[Baekjoon] 2231번 분해합 (C++, Python)

 

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

2231번: 분해합

 

 

C++

전체 다 계산하는 것은 시간초과가 걸립니다. 거꾸로 조사한다고 하더라도 가장 작은 생성자를 구해야합니다. 여기서 중요한 것은 얼마만큼 계산해야하냐는 것인데 숫자에 대한 특성을 자세히 보면 N이라는 자기 자신에 각 자리 숫자를 더한다는 것을 확인할 수 있습니다.

 

즉, 자기 자신 + 자리 수 + 자리 수 .... 입니다.

여기서 자리 수 중 가장 큰 숫자는 9이며 이것이 N의 길이*9만큼의 숫자가 계산해야하는 총 양입니다.

 

예를 들어 216은 3자리 숫자이며 215부터 3*9 = 27개의 숫자의 분해합을 구하면 가장 작은 생성자를 구할 수 있습니다.

즉, 만약 생성자가 존재할 때 187~215 중 분해합을 진행하면 N과 같은 숫자가 무조건 존재합니다.

 

 

 

방법 1 - 2020KB, 0ms, 485B

 

 

 

초기방법

#include <iostream>
using namespace std;
int main(){
	int n, i, s;
	cin >> n;
	
	if (n < 18){
		for (i=n-1; i > 0; i--){
			s = i + i/10 + i%10;
			if (s==n)
				break;
		}
		cout << i;		
	}
	else{	
		int len=0, t, w=-1, tmp=n;
		while (tmp/10) {
			tmp /= 10;
			len++;	
		}		
		for (int i=n-1; i >= n-9*(len+1); i--){
			s = i;
			t = i;			
			while (t/10){
				s += t%10;
				t /= 10;
			}
			s += t;
			if (s == n) w = i;			
		}		
		if (w==-1) cout << 0;
		else cout << w;			
	}	
}

 

방법 2 - 1112KB, 0ms, 241B

방법 1과 다르게 작은 것부터 세면 빠르게 종료가능

 

 

#include <stdio.h>
int main(){
	int n,s,t,l=0,i,w=0;
	scanf("%d",&n);
	t=n;
	while(t>0){
		t/=10;
		l++;
	}
	for(i=n-9*l;i<=n;i++){
		s=i;
		t=i;
		while(t>0){
			s+=t%10;
			t/=10;
		}
		if(s==n){
			w=i;
			break;
		}
	}
	printf("%d",w);
}

 

 

방법 3 - 1112KB, 0ms, 146B

 

#include <stdio.h>
main(){int n,s,t,i,w=0;scanf("%d",&n);for(i=n-54;i<n;i++){s=i;t=i;while(t){s+=t%10;t/=10;}if(s==n){w=i;break;}}printf("%d",w);}

#include <stdio.h>
main(){
	int n,s,t,i,w=0;
	scanf("%d",&n);
	for(i=n-54;i<n;i++){
		s=i;t=i;
		while(t){
			s+=t%10;
			t/=10;
		}
		if(s==n){
			w=i;
			break;
		}
	}
	printf("%d",w);
}

 

어차피 t<0이면 자동 중지되므로 초기 for문에 i가 음수로 들어가도 무방

 

Python

 

방법 1

sum(map(int, str(N)))

= N의 각 자리수를 더한 값 

 

n = int(input())
for i in range(max(1, n-54),n):
    if sum(map(int,str(i)))+i == n:
        print(i)
        exit(0)
print(0)

 

 

방법 2

 

 

 

방법 3