[백준, Java] 1441번, 나누어 질까(정수론)

문제 링크

1441번: 나누어 질까

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

1. L부터 R이하의 양의 정수가 존재합니다.

2. N크기의 정수를 가진 숫자 배열 A가 존재합니다.

3. L~R까지의 수 중 A의 배열값에 적어도 하나는 나누어떨어지는 수의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 나눠떨어지는 개수를 탐색합니다.

 

3. 나눠떨어지는 숫자의 개수를 결과로 출력합니다.

 

 

나눠떨어지는 수 탐색

 

정수론에서 100이하의 양수 중, 2로 나누어 떨어지는 개수

→ 즉, 2의 배수의 개수 : 100 ÷ 2 = 50개입니다.

 

위 방법을 이용하면, 각 카드가 1 ~ N까지 나눠떨어지는 개수를 알 수 있습니다.

 

하지만, 해당 값 중에서는 중복되는 값들이 존재할 것입니다.

 

중복되는 값을 찾는 것에서는 최소 공배수를 이용하여 구분하였습니다.

 

최소 공배수 점화식

 

lcm : a × b / gcd(a, b)

 

※ GCD : 최대 공약수

 

최대 공약수를 구하는 방법은 유클리드 호재법을 사용하였습니다. 자세한 정보는 아래 링크를 통해 개념을 학습하시는 것을 추천드립니다.

 

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

 

 

 

그러면, 최소 공배수만 구하면 되는 것이냐???

 

아닙니다!!, 최소 공배수 사이에도 중복되는 수들이 발생하기 때문입니다.

 

그러면... 어떻게 구분을 해야 하는가.... 포함배제의 원리를 사용해야 합니다.

 

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

 

 

포함배제의 원리 + 최소 공배수(LCM)을 통한 백트래킹 + 비트마스킹을 이용해서 탐색을 문제를 해결하였습니다.

 

포함배제의 원리를 이용하여 2가지 경우로 나눌 수 있습니다.

 

1. 홀수 개수의 최소 공배수일 때

 

→ 결과 += n / 최소 공배수

 

2. 짝수 개수의 최소 공배수일 때

 

→ 결과 -= n / 최소 공배수

 

예제입력 1.

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

 

N : 2

 

L : 1

 

R : 1000000000

 

 

A[]

 

2

3

 

2. 나눠떨어지는 개수를 탐색합니다.

 

 

비트마스킹 : 01

 

선택한 수 : { 2 }

 

개수 : 1000000000 ÷ 2 - (1 - 1) ÷ 2 = 500000000 - 0 = 500000000개

 

홀수 개의 최소 공배수이므로 덧셈을 합니다.

 

 

 

비트마스킹 : 10

 

선택한 수 : { 3 }

 

개수 : 1000000000 ÷ 3 - (1 - 1) ÷ 3 = 333333333 - 0 = 333333333개

 

홀수 개의 최소 공배수이므로 덧셈을 합니다.

 

 

 

비트마스킹 : 11

 

선택한 수 : { 2, 3 }

 

최소 공배수 : 2 × 3 ÷ GCD(2, 3) = 2 × 3 ÷ 1 = 6

 

개수 : 1000000000 ÷ 6 - (1 - 1) ÷ 6 = 166666666 - 0 = 166666666개

 

 

짝수 개의 최소 공배수이므로 뺄셈을 합니다.

 

 

3. 나눠떨어지는 숫자의 개수를 결과로 출력합니다.

 

얻은 개수들을 연산 진행

 

500000000 + 333333333 - 166666666 = 666666667

 

666666667을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 A[]와 N, L, R을 띄어쓰기 기준 나누었습니다.
• search함수를 실행하여 나눠떨어지는 수를 탐색합니다.
• 탐색이 끝난 뒤 나눠떨어지는 수의 개수를 결과로 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 포함배제의 원리와 최소 공배수를 이용한 백트래킹으로 나눠떨어지는 수를 탐색합니다.
• lcm함수는 gcd함수를 이용하여 최소 공배수 점화식을 진행합니다.
• gcd함수는 유클리드 호재법을 이용하여 최대 공약수를 구합니다.

결과코드

import java.io.*;
import java.util.*;


public class Main {
    static int fullMask;	//모든 A 배열 사용 관련 BitMask
    static int N, L, R, result;
    static boolean[] using;	//비트 마스킹 중복 여부 확인
    static int[] A;
    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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        A = new int[N];
        fullMask = (1<<N)-1;
        using = new boolean[fullMask+1];
        st = new StringTokenizer(br.readLine()," ");
        //A[] 배열 입력값 저장
        for(int i=0;i<N;i++){
            A[i] = Integer.parseInt(st.nextToken());
        }
        //나누어 떨어지는 수 찾기 진행
        for(int i=0;i<N;i++){
          search(1<<i, A[i],  1);
        }
        //나누어 떨어지는 수의 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백트래킹 + 비트마스킹을 이용한 나누어 떨어지는 수 탐색하는 함수
    static void search(int bitmask, long cur, int cnt){
        //이미 방문한 비트마스킹일 때
        if(using[bitmask]){
            return;
        }
        using[bitmask] = true;
        //더 이상 나누어 떨어질 수 없을 때
        if(cur > R){
            return;
        }

        //비트 수의 따른 결과값 더하기(포함 배제의 원리)
        long val = R/cur - (L-1)/cur;
        if(cnt % 2 == 0){
            result -= val;
        }else{
            result += val;
        }
        using[bitmask] = true;
        //모든 수의 최소 공배수 했을 때
        if(bitmask == fullMask){
            return;
        }
        //다른 공배수와 합치기 진행
        for(int i=0;i<N;i++){
            if((bitmask & (1<<i)) == 0){
                search(bitmask | (1<<i), lcm(cur, A[i]), cnt+1);
            }
        }
    }
    //GCD와 점화식을 이용해서 최소 공배수 함수
    static long lcm(long a, long b){
        return a*b/gcd(a,b);
    }
    //최대 공약수 구하는 함수(유클리드 호재법)
    static long gcd(long a, long b){
        if(b==0) return a;
        return gcd(b,a%b);
    }
}