[BOJ] 2231 - 누적합 (Java)

알고리즘

• 브루트포스 알고리즘

1. 문제

2. Idea

• 주어진 수 n에 대해 적절한 범위 내에서 모든 가능한 분해합을 찾고, 그 중에서 원래 수 n과 같은 값을 찾는 방법

3. 풀이

3.1. 변수 선언 및 초기화

• n 입력

• result=결과값을 저장할 변수로 초기화합니다.

• n_length=n의 자릿수 -> 분해합을 계산할 범위 설정

int n = sc.nextInt();
int result = 0;
int n_length = String.valueOf(n).length();

3.2. for문 수행

• i 초기화

• i = n보다 작은 범위에서 증가하며 반복

  • n의 자릿수에 9를 곱한 값보다 크지 않도록 설정

  • (이유) 분해합을 찾을 때, n의 자릿수만큼 9를 더해도 n보다 작아지지 않는 범위에서 찾기 때문

for (int i = Math.max(1, n - (n_length * 9)); i < n; i++){...}

3.3. 누적합 계산

• 각 i에 대해, number 변수를 사용하여 i를 복사하고, sum 변수를 사용하여 각 자릿수의 합 계산

int number = i;
int sum = 0;

• while 반복문을 사용하여 number를 10으로 나누면서 각 자릿수를 더하고 number를 감소시킴

while (number != 0) {
	sum += number % 10;
	number /= 10;
}

• if 문을 사용하여 n==i+sum -> i를 result에 저장, 반복문 break

if (sum + i == n) {
	result = i;
	break;
}

3.4. 결과 출력

System.out.println(result);

4. 전체코드

package week3;
//Bronze_분해합
import java.util.*;
public class BOJ_2231 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int result = 0;
        int n_length = String.valueOf(n).length();

        for (int i = Math.max(1, n - (n_length * 9)); i < n; i++) {
            int number = i;
            int sum = 0;

            while (number != 0) {
                sum += number % 10;
                number /= 10;
            }

            if (sum + i == n) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}