[백준, Java] 24551번, 일이 너무 많아..., (정수론)

문제 링크

24551번: 일이 너무 많아...

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 2개 이상의 숫자 1로만 이루어진 수를 싫어하며, 해당 수를 약수로 가진 수도 싫어한다.

2. 1 ~ N까지의 정수 중 2개 이상의 1로 이루어진 수를 약수로 가지는 수의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 포함 배제의 원리를 이용해서 2개 이상의 1로 이루어진 수를 약수로 가지는 개수를 탐색합니다.

 

3. 탐색을 통해 얻은 약수를 지니는 수의 개수를 결과로 출력합니다.

 

2개 이상의 1로 이루어진 약수의 개수 탐색(포함 배제의 원리)

 

 

 

1 ~ N 범위에 대해서 약수의 개수를 구하는 방법

 

점화식 : N / 약수의 값

 

※ 나누기 결과는 해당 배수의 개수를 뜻하기 때문에 약수의 개수라고 표현할 수 있습니다.

 

 

우리는 1이 2개 이상인 정수에 대해서 약수인 것을 찾아야 합니다.

 

1이 2개 이상인 정수 : {11, 111, 111, 1111, 11111, ....}

 

1 ~ 220의 범위에서 11의 약수의 개수 : 220 / 11 = 20개

 

이렇게, 각 1이 2개 이상의 정수에 대한 약수를 구하면 끝이 나는 것은 아닙니다.

 

왜냐하면, {11, 111, 1111.. } 등 공배수에 따른 개수를 제거해주어야 하기 때문입니다.

 

여기서 포함 배제의 원리를 사용하였습니다.

 

 

포함 배제의 원리

포함배제의 원리 - 위키백과, 우리 모두의 백과사전

 

교집합을 구할 때에는 같은 약수를 가리킨 값으로써, 최소 공배수로 N을 나눈 것이 교집합이 됩니다. 

 

 

최소 공배수 : n1 × n2 ÷ 최대 공약수

 

 

즉, 최대 공약수는 유클리드 호제법을 이용해서 쉽게 구할 수 있습니다.

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

 

이 조건들을 이용해서 포함 배제의 원리의 결과값을 출력하면 2개 이상 1로 이루어진 약수의 개수를 구할 수 있습니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 111

 

 

 

2. 포함 배제의 원리를 이용해서 2개 이상의 1로 이루어진 수를 약수로 가지는 개수를 탐색합니다.

 

1 ~ N(111)범위에서 2개 이상의 1로 이루어진 수 : { 11, 111 }

 

포함 배제의 원리 진행

 

P(11 U 111) = P(11) + P(111) - P(11 ∩ 111)

 

 

※ LCD : 최소 공배수

 

※ GCD : 최대 공약수

 

 

P(11) : N(111) / 11 = 10개

 

P(111) : N(111) / 111 = 1개

 

P(11 ∩ 111) : 

 

GCD(11, 111) : 1221

 

LCD(11, 111) : 11 × 111 ÷ GCD(11, 111) = 11 × 111 ÷ 1 = 1221 

 

약수의 개수 : N(111) / 1221 = 0개

 

 

 

P(11 U 111) = P(11) + P(111) - P(11 ∩ 111) = 10 + 1 - 0 = 11개

 

 

 

3. 탐색을 통해 얻은 약수를 지니는 수의 개수를 결과로 출력합니다.

 

 

포함 배제의 원리를 이용한 탐색으로 얻은 약수의 개수 : 11개

 

 

11 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 1 ~ N까지 2개 이상 1로만 이루어진 수를 구합니다.
• search를 이용하여 1로만 이루어진 수로 나누어지는 약수의 개수를 탐색합니다.
• 탐색한 약수의 개수를 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 포함 배제의 원리를 이용해서 약수의 개수를 탐색합니다.
• search함수는 교집합은 최소 공배수이기 때문에 GCD 함수와 최소 공배수 점화식을 통해 구합니다.
• GCD함수는 유클리드 호제법을 이용하여 최대 공약수를 구합니다.

 

※ 이 문제는 long 형을 벗어날 수 있기 때문에 BigInteger을 사용하였습니다.

결과코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static long result = 0;
    static long N, size;
    static List<Long> sameNumber;	//2개 이상 1로만 이루어진 수 저장 List
    static BigInteger maxValue;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Long.parseLong(br.readLine());
        sameNumber = new ArrayList<>();
        //2개 이상 1로 이루어진 수(1 ~ N) 탐색
        long num = 11;
        while(num <= N){
            sameNumber.add(num);
            num = num * 10 + 1;
        }
        size = sameNumber.size();
        //1 ~ N의 범위 최대값 : N
        maxValue = new BigInteger(String.valueOf(N));
        //포함 배제의 원리로 약수의 개수 탐색
        search(1, 0, 0);
        //약수의 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //포함 배제의 원리를 이용하여 약수의 개수를 구하는 함수
    static void search(long cur, int cnt, int idx){

        //더 이상 추가적으로 2개 이상 1로만 이루어진 수가 없을 때
        if(idx == size){
            return;
        }

        //다음 탐색할 수와 현재 값에 대한 최대 공약수 구하기
        long nxtGcd;
        if(cur >= sameNumber.get(idx)){
            nxtGcd = gcd(cur, sameNumber.get(idx));
        }else{
            nxtGcd = gcd(sameNumber.get(idx), cur);
        }

        //long 범위를 벗어날 수 있기 때문에 BigInteger 형변환
        BigInteger bigCur = new BigInteger(String.valueOf(cur));
        BigInteger bigNxtVal = new BigInteger(String.valueOf(sameNumber.get(idx)));
        BigInteger bigGcd = new BigInteger(String.valueOf(nxtGcd));
        //교집합 : 최소 공배수 -> n1 × n2 ÷ GCD(n1, n2)
        BigInteger bigNxtLcd = bigCur.multiply(bigNxtVal).divide(bigGcd);
        //만약 최대값 보다 작을 경우, 최소 약수의 개수가 1개 이상이다.
        if(bigNxtLcd.compareTo(maxValue)<= 0){
            long nxtLcd = bigNxtLcd.longValue();
            //포함 배제 원리에 따라 교집합의 개수가 짝수, 홀수일 때 구분
            int nxtCnt = cnt+1;
            if(nxtCnt % 2 == 1){
                result += N / nxtLcd;
            }else{
                result -= N / nxtLcd;
            }
            //해당 수를 교집합으로 사용했을 때 다음 탐색 진행
            search(nxtLcd, nxtCnt, idx+1);
        }

        //해당 수를 교집합으로 사용하지 않았을 때 다음 탐색 진행
        search(cur, cnt, idx+1);
    }
    //유클리드 호제법을 이용한 최대 공약수 구하는 재귀 함수
    static long gcd(long a, long b){
        if(b == 0){
            return a;
        }
        return gcd(b, a % b);
    }
}