• 백준 6378번 디지털 루트 :: 마이구미
    알고리즘 풀이/수학 2017. 11. 12. 22:31
    반응형

    이 글은 백준 알고리즘 문제 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    // 공식 활용
    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());
    }
    cs


    반응형

    댓글

Designed by Tistory.