[백준 2331 Java] 분해합 / 각 자리의 합 구하기

브루트 포스란?

단순 무식한 알고리즘

문제를 해결하기 위해 가능한 모든 경우에 대해 직접 시도하는 방법으로 완전 탐색이라고도 함

 

 

이 문제를 풀 때, 1~1,000,000의 분해합을 모두 구해서 배열에 넣고 그 배열의 요소 중

사용자가 입력한 값이랑 일치하는 요소를 찾아서 그 요소의 인덱스 번호 중 가장 작은 값을 뽑아내려고 했다. 

이 방법이 맞는지도 의문일 뿐더러, 어찌저찌 답은 나오더라도 아주 아주 비효율 끝판왕의 코드가 되기 때문에

단순하게 작은 수부터 분해합을 계산하기 시작해서 사용자가 입력한 값과 일치하는 값이 나오면

그 수가 정답이기 때문에 전부 다 계산하면서 힘을 뺄 필요가 없다...ㅠ_ㅠ

 

 

코드를 살펴보면서 이해를 해보자.

 

import java.util.Scanner;

// n을 입력받아 n의 가장 작은 생성자를 찾아라
public class Ex2 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int result = 0; // 가장 작은 생성자가 담길 변수
		
		// i는 생성자 (생성자는 무조건 n보다 작으므로 n보다 작을 때까지 돌리기)
		for(int i = 0; i < n; i++) { 
			
			int sum = 0; // 각 자릿수 합 변수
			int number = i;
			
			// 각 자릿수 더하기
			while(number != 0) {
				sum = sum + (number % 10);
				number = number / 10;
			}
			
			// i 값과 각 자릿수 누적합이 같을 경우 (생성자를 찾았을 때)
			if(sum + i == n) {
				result = i;
				break;
			}
			
		}
		
		System.out.println(result);
	
	}	

}

 

+ 각 자릿수의 합을 구하는 공식을 참고하자.

 

import java.util.Scanner;

public class Ex2_1 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt(); // while문을 돌고 나면 남아 있는 숫자들이 담긴 변수
		int sum = 0; // 남은 숫자들 중 마지막 자리의 숫자
		
		// 12345를 입력했다고 가정하자
		
		while(num != 0) { // num이 0이 아닐때까지 반복
			
			sum += num % 10;	// num을 10으로 나눈 나머지를 sum에 저장
			 			// 첫 번째 바퀴에서는 12345에서 5가 sum에 저장
			
			num /= 10;  		// num을 10으로 나눈 값을 다시 num에 저장
			 			// 첫 번째 바퀴에서는 12345에서 1234가 num에 저장
							
			 			// 이 과정을 반복하다보면 5바퀴를 돌게 되고		
		}
		
		System.out.println(sum); // sum의 값을 출력하면 각 자리 숫자의 누적합을 구할 수 있다
	
	}	

}