[BOJ] 2231번: 분해합 (Java)

https://www.acmicpc.net/problem/2231

---

자연수 N이 주어졌을 때 M이라는 숫자가 만약 N의 생성자라면, M의 각 자리 수와 M을 합한 값이 N과 같다.
N의 생성자 M, 그리고 M의 분해합은 N인 관계가 된다.

분해합과 생성자의 관계

 

어떤 수의 생성자는 여러 개일 수도 있고 아예 없을 수도 있다. 만약 어떤 수의 생성자가 여러 개라면 가장 작은 값을 출력해내면 된다.
생성자가 존재하지 않는다면 0을 출력하자.

 

문제 예시로는 N = 216, M = 198이 나와있다. 1+9+8+198=216 이렇게 계산할 수 있다.

 

처음 이 문제를 접했을 때 내가 고민한 관건은

 

💭 고민

1️⃣ M이라는 숫자를 찾기 위해 순차 탐색을 할 것인가
2️⃣ 어떻게 M의 각 자리수를 쪼개낼 수 있을 것인가

 

이 두 가지였다.

 

✏️ 해결

1️⃣ M이라는 숫자를 찾기 위해 순차 탐색을 할 것인가

순차 탐색을 하면 시간복잡도가 O(n^2)이 되기에, 혹여나 코드 시간 초과가 발생할까 싶어 걱정했다.

하지만 N의 크기가 커질 수록 N의 생성자 M도 N과 가깝게 커질 것이다. 그래서 순차적으로 M을 찾는 for문에서, 1에서부터 찾는 것이 아니라 N-1부터 1씩 줄여가며 뒤에서부터 찾아볼까도 싶었다. 근데 뒤에서부터 M을 찾는다면 가장 큰 생성자를 먼저 찾게 될테다. M은 N의 가장 작은 생성자이어야 하므로 가장 작은 생성자를 찾을 때까지 이것을 반복하나, 그냥 1에서부터 찾다가 생성자를 찾는 순간 반복문에서 탈출하던지, 어쨌든 순차 탐색이라는 점에서 시간 초과 면에서는 대동소이할 것만 같은 느낌이 들었다...

 

그래서 일단 그냥 순차 탐색으로 결정!

(하지만 보다 효율적인 알고리즘을 짜고 싶다면 당연히 수정해야할 것이다...)

 

 

2️⃣ 어떻게 M의 각 자리수를 쪼개낼 수 있을 것인가

이제서야 본 게임이다. 

어떻게 하면 숫자를 각 자리로 쪼개서 더할지 고민을 거듭했다. 사실 처음에는 각 자리로 떼어내자!에만 혈안이 되어 나누고 나머지를 구하고 규칙성을 못 찾고 있었다. 하지만 나는 코드를 짜야하는 사람이다. 어떻게 코드로 만들어낼지 고민하는 것은, 그저 마구잡이로 계산해보는 게 아니라 코드화 시킬 수 있는 수식을 찾아내야 하는 것 같다.

 

여튼간 반복문을 써야만 할 것 같은 느낌은 들었다만, 마구잡이로 나누고 나머지를 구하고 하다보니 뭔가 반복되고 있다는 것을 알아차렸다.

재귀함수로 나타낼 수 있겠다 싶었고 재귀함수 코드 생김새를 머릿 속에서 그리면서... 식을 정리할 수 있었다! 휴

 

결론적으로 다음과 같은 코드를 짰다.

import java.util.Scanner;

public class BOJ_2231 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = 0;

        for (int i = 1; i < N; i++) {
            if(i + sumOfDigits(i) == N){
                M = i;
                break;
            }
        }

        System.out.println(M);
    }

    public static int sumOfDigits(int i) {
        if (i==0)
            return 0;
        else
            return i%10 + sumOfDigits(i/10);
    }
}

 

 

M의 뒷자리부터 차례로 더한 값을 구하는 sumOfDigits 메서드를 만들었다.

예를 들어 i가 198이라면
else문에서 198%10(= 8) + sumOfDigits(198/10) 재귀 호출
-> 19%10(= 9) +  sumOfDigits(19/10) 재귀 호출
-> 1%10(= 1) +  sumOfDigits(1/10) 재귀 호출
-> i가 0이 되어 return 0으로 종료

 

이런 식이 될 것이다.

 

8+9+1(각 자리 수)을 더한 값과 본래 i(M)을 더하면 분해합 N 완성! 

생성자 M을 찾았기에 반복문을 탈출하고 이대로 M을 출력한다.

만약 생성자가 없는 수라면 반복문을 다 돌고, M의 초기값을 0으로 두었기에 0이 출력된다.

 

public static int sumOfDigits(int i) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        return sum;
}

sumOfDigits을 재귀함수가 아니라 일반 반복문으로 나타내면 위와 같다. 난 뭔가 이게 더 헷갈린다...

 

앞서 언급했듯이 이번 문제에서 느낀 점은 나는 코드를 짜야하는 사람이니 어떻게 코드로 만들어낼지 고민해야한다는 것이다. 규칙성이나 식을 찾고자 할 때 재귀함수 형태로 식을 나타내었던 것처럼, 코드화 시킬 수 있는 수식을 찾기 위해 노력해보자!