[JAVA] 백준 17618번: 신기한 수

17618번: 신기한 수

문제

평소에 수에 대한 관심이 많은 아이인 민철이는 오늘도 노트에 연필로 수를 더하거나 빼거나 곱하거나 나눠보면서 시간을 보내고 있다. 그러다가 18이라는 수는 신기한 성질을 가진다는 것을 알아냈다. 18을 이루는 각 자릿수인 1과 8을 합한 9는 18의 약수가 된다.

민철이는 18과 같이 모든 자릿수의 합으로 나누어지는 수를 여러 개 더 찾아냈는데, 12, 21도 그런 신기한 수였다. 민철이는 이렇게 모든 자릿수의 합으로 나누어지는 수를 “신기한 수”라고 부르기로 했다. 민철이는 더 큰 신기한 수를 찾아보기도 했는데 1729도 신기한 수라는 걸 알아내었다. 1729는 1+7+2+9=19로 나누어진다.

민철이는 신기한 수가 얼마나 많은지 알고 싶었다. 주어진 자연수 N에 대해 N이하인 신기한 수는 총 몇 개인지 궁금했다. 하지만 N이하의 모든 수에 대해서 신기한 수인지 아닌지를 손으로 알아내기는 시간이 너무 오래 걸렸다.

여러분은 민철이를 도울 수 있는 프로그램을 작성해야 한다. 입력으로 1 이상인 자연수 N이 주어질 때 N 이하인 신기한 수의 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정수 N (1 ≤ N ≤ 10,000,000) 하나가 주어진다.

출력

N 이하인 신기한 수의 개수를 정수로 출력한다.

 

---

단순하게 정수의 자릿수별로 더해서 본래의 값에 나누어 나누어떨어지면 신기한 수 인것이다.

---

문제풀이1

import java.util.Scanner;

public class BJ_CT_1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int count =0;

        for(int i=1;i<=n;i++){
            String str = Integer.toString(i); //i를 문자열로 받음
            String[] arr= str.split(""); //split을 사용해 문자별로 배열에 담음
            int sum=0;
            for(int j=0;j<arr.length;j++){
                sum+=Integer.parseInt(arr[j]); //자릿수의 합을 sum에 누적
            }

            if(i%sum==0) count++; //신기한 수 이면 count++
        }

        System.out.println(count);

    }

}

로직은 맞지만 배열에 담아서 하다보니 시간초과가 나왔다.. 🤮

그래서 주먹구구식 방식 말고 좀 더 수학적으로 접근해 보았다.

 

문제풀이2

import java.util.Scanner;

public class BJ_CT_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num= sc.nextInt();
        int count=0;

        for(int i=1;i<=num;i++){
            int sum =0;
            int n=i;

            while(n!=0){
                sum+=n%10; //정수에 %10 을 해주면 맨마지막 자릿수가 나오고
                n=n/10; //나머지 값으로 맨마지막 자릿수를 뺀 값이 나온다
            }

            if(i%sum==0) count++; //신기한 수 라면 count++

        }
        System.out.println(count);
    }
}

이 로직은 정수를 자릿수 별로 알 수 있는 방법으로 유용하게 쓰이니 알고 있으면 아쥬 좋습니당

 

 

통과!!