어떤 자연수 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을 출력한다.
예제 입력
216
예제 출력
198
이게 왜 틀리는거지..? => 자연수 모든 범위를 생각 안했자나 ㅎㅎ;
그럼 모든 자연수에 대해서 진행할려면.. 재귀함수?하기에는 너무 투머치고
그냥 루프를 돌면서 10으로 나누고 %10으로 나머지를 확인하면 되겠다
근데 왜 답이 안나올까.... 중요한 알고리즘구현은 잘한거같은데
2번째 시도 -> 무식하게 각 자리수를 먼저 계산하고, 각 자리수에 맞춰서 진행하려고 했는데 그러기에는 경우의 수가 너무많았다..
자리수를 구하는 형식(암기해두면 많이 편하겠다!)
int num;
for(int i=0; i<N; i++){
int tmp = i;
int sum = i;
while(tmp>0){
//10으로 나눈 나머지를 이용해서 1의자리 수부터 하나하나 끄집어내고,
//다음으로 진행하기 위해서 10으로 나눠줌
sum = sum + tmp%10;
tmp = tmp / 10;
}
}
이러고 출력을 하는 위치를 헷갈렸었다.
최소값을 구해야하기 때문에 값을 구하는 과정에서 맨 처음에 원래의 값인 N이 나오면 반복문을 탈출하고 프린트해줘야한다!
풀이
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int ans =0;
//주석한게 내가한 방법
//왜 sum에다가 i를 넣고 시작하는가
for(int i=1; i<N; i++){
int sum = i;
int tmp = i;
//sum = i + i/100 + (i/10)%10 + i%10%10;
while(tmp>0){
sum = sum +tmp%10;
tmp = tmp/10;
}
if(sum == N){
ans = i;
break;
}else{
ans = 0;
}
}
System.out.println(ans);
}
}
2번째 시도
이전에 공부했던 자리수 구하기를 생각해서 문제에서 제시한 총 자릿수까지 가정해서 덧셈을 진행했다.
-> 어짜피 만약에 적은 자리수가 나오는 경우에는 어짜피 나중에 자리수계산하는 부분들이 0이 되기 때문에 문제없다!
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(bf.readLine());
int sum = 0;
for(int i=0; i<n; i++){
if(n == i + i%10 + i/10%10 + i/100%10 + i/1000%10 + i/10000%10 + i/100000%10 + i/1000000%10){
sum = i;
break;
}
}
if(sum == 0)
bw.write(Integer.toString(0));
else
bw.write(Integer.toString(sum));
bw.flush();
}
}