백준 6378번 디지털 루트 :: 마이구미

이 글은 백준 알고리즘 문제 6378번 "디지털 루트" 를 풀이한다.

문제는 단순한 구현이지만, 디지털 루트란 용어와 관련 공식이 실제로 존재하기 때문에 다루게 되었다.

위키 - https://en.wikipedia.org/wiki/Digital_root

문제 링크 - https://www.acmicpc.net/problem/6378

양의 정수 N의 디지털 루트를 구하려면 N을 이루고 있는 모든 자리수를 더해야 한다. 이 때, 더한 값이 한 자리 숫자라면, 그 수가 N의 디지털 루트가 된다. 두 자리 이상 숫자인 경우에는 다시 그 수를 이루고 있는 모든 자리수를 더해야 하며, 한 자리 숫자가 될 때 까지 반복한다.

24의 디지털 루트를 구해보자. 2+4=6이다. 6은 한 자리 숫자이기 때문에, 24의 디지털 루트는 6이 된다. 39의 경우에는 3+9=12이기 때문에, 한 번 더 더해야 한다. 따라서, 1+2=3이 디지털 루트가 된다.

양의 정수 N이 주어졌을 때, 그 수의 디지털 루트를 구하는 프로그램을 작성하시오.

여러 곳에서 위와 같은 문제를 볼 수 있듯이, 대중화된 문제이다.

대부분의 풀이는 문자열로 만든 후, 쪼개서 합을 구하는 과정을 반복해 해결한다.

String[] s = n.split("");
int sum = 10;

while (sum >= 10) {
    sum = 0;

    for (int i = 0; i < s.length; i++) {
        sum += Integer.parseInt(s[i]);
    }

    s = String.valueOf(sum).split("");
}

다른 방법으로는 디지털 루트의 공식이 존재한다.

입력이 최대 1000자리이기 때문에, BigInteger을 사용해주면 공식을 통해 문제를 해결할 수 있다.

BigInteger bi = new BigInteger(n);
bi.subtract(BigInteger.ONE).mod(new BigInteger("9")).add(BigInteger.ONE);

알아두면 좋은 공식이다.

공식을 이해하는 것도 중요하기 때문에, 디지털 루트에 관해 깊게 이해한 후, 증명을 다루는 글을 계획(만) 하고 있다.

Github - https://github.com/hotehrud/acmicpc/tree/master/math

// 공식 활용
private void solve() {
    String n = "";
    StringBuilder sb = new StringBuilder();
    while (!(n = sc.readLine()).equals("0")) {
        BigInteger bi = new BigInteger(n);
        sb.append(bi.subtract(BigInteger.ONE).mod(new BigInteger("9")).add(BigInteger.ONE) + "\n");
    }
    System.out.println(sb.toString());
}
 
// split 활용
private void solve() {
    String n = "";
    StringBuilder sb = new StringBuilder();
 
    while(!(n = sc.readLine()).equals("0")) {
        String[] s = n.split("");
        int sum = 10;
 
        while(sum >= 10) {
            sum = 0;
 
            for(int i=0;i<s.length;i++) {
                sum += Integer.parseInt(s[i]);
            }
 
            s = String.valueOf(sum).split("");
        }
        sb.append(sum + "\n");
    }
    System.out.println(sb.toString());
}