백준 2231번 : 분해합 (JAVA) 문제 풀이

www.acmicpc.net/problem/2231

2231번: 분해합

---

 

 

 

 

문제 분석

분해합은 아래처럼 자기 자신과 각 자릿수를 더한 것
256 분해합 : 256 + 2 + 5 + 6 = 269 

문제에서 분해합은 예를 들어 256을 자리수로 쪼개서 더하고, 다시 256을 더한게 분해합이라고 한다.

 

생성자 란?
269 = 256 + 2 + 5 + 6

256을 분해합을 해서 나온 수가 269일 때, 256은 269의 생성자가 된다.

 

생성자를 구하는 방법은 1부터 N까지 돌면 오래 걸리니까, 시간복잡도를 줄이기 위해서 N/2 부터 시작을 해서

분해합을 구해서 그 수가 생성자가 되는지 확인하면 된다. (작은 수 부터 시작을 해서, 가장 작은 생성자를 찾는 조건은 만족이 된다.)

 

    int N = sc.nextInt();
    int result = 0;
 
    for(int i=N/2; i< N; i++){
        result = i;
 
        // 각 자리수 더하기
          
        if(result == N){
            System.out.println(i);
            break;
        }
    }

 

각 자리수 더하기

    int MOK = 0; // 몫
    int NMG = 0; // 나머지
        
    for(int i=N/2; i< N; i++){
        int result = i;
        int temp = i; // 연산하기 위한 temp 변수
        while(temp >= 10){
            MOK = temp / 10;
            NMG = temp % 10;
 
            result += NMG;
            temp /= 10;
        }
        result += temp;
 
            if(result == N){ // N과 같아 지는 시점에 출력하고 종료
                System.out.println(i);
                break;
            }
    }

 

 

 

전체 코드

import java.util.*;
 
public class Main {
    public static void main(String[] args){
    //this class For print
    Scanner sc = new Scanner(System.in);
    int NMG = 0;
    int MOK = 0;
 
    int N = sc.nextInt(); // 124
    int result = 0;
    int temp = 0;
 
    for(int i=N/2; i< N; i++){
        temp = i; // 116
        result = i; // 116
 
        while(temp >= 10){
            MOK = temp / 10; // 1
            NMG = temp % 10; // 1
 
            result += NMG; // 123
            temp /= 10; // 1
        }
        result += temp;
 
        if(result == N){
            System.out.println(i);
            break;
        }
    }
    if(result != N)
        System.out.println("0");
    }
}