분해합(2231)

모든 경우를 시도하여 N의 생성자를 구하는 문제

문제

어떤 자연수 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();
    }
}