[자바] 백준 17436 - 소수의 배수 (java)

목차

문제 : boj17436

 

 

필요 알고리즘

• 포함 배제의 원리 (inclusion and exclusion)
  
  • 포함 배제의 원리로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  예제 입력 2를 생각해보자.

2 100
2 3

 

  직관적으로 우린 이걸 푸는 방법을 알고 있다. 100 이하의 자연수 중 2로 나누어 떨어지는 수는 100/2 = 50개가 존재한다. 그리고 3으로 나누어떨어지는건 100/3 = 33개가 존재한다. 그리고 둘이 중복으로 세어버린 100/(2x3) = 16개는 빼줘야한다. 최종적으로 50 + 33 - 16 = 67이 답이다.

 

  3개라면 어떨까? 주어진 소수가 A, B, C 라고 한다면

100/A + 100/B + 100/C - 100/(AB) - 100/(BC) - 100/(AC) + 100/(ABC) 가 될 것이다.

이걸 일반화해서 4개, 5개, ... 에 대해서도 정의한게 포함 배제의 원리이다. 결론적으로 그냥 홀수 개의 교집합은 더하고, 짝수 개의 교집합은 빼면 된다.

long answer = 0l;
for (int i = 1; i <= n; i++) {
    long tmp = solve(-1, i, 1);	// i개의 교집합으로 셀 수 있는 경우의 수
    
    if (i%2==1) answer+=tmp;	// 홀수 교집합이면 더하고
    else answer-=tmp;	// 짝수 교집합이면 뺀다
}
System.out.println(answer);

 

  개념적인 부분 보다는 재귀를 안쓰면 상당히 코드가 복잡해지므로 특정 x개의 교집합을 만드는 부분에서 구현이 좀 어려울 순 있다. 재귀가 익숙하지 않다면 디버깅을 걸어서 한번 어떤식으로 동작하는지 한 단계씩 생각해보자. 그리고 이 문제는 모든 입력값이 모두 다르고, 소수라서 별 문제 없었는데 그게 아니라면 좀 더 귀찮아진다.

private long solve(final int bf, final int cnt, final long mult) {
    if (cnt == 0) {
        return m/mult;
    }

    long result = 0l;
    for (int i = bf+1; i <= n-cnt; i++) {
        result += solve(i, cnt-1, mult*arr[i]);
    }
    return result;
}

 

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private long[] arr;
    int n;
    long m;

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Long.parseLong(st.nextToken());
        arr = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }

        long answer = 0l;
        for (int i = 1; i <= n; i++) {
            long tmp = solve(-1, i, 1);
            if (i%2==1) answer+=tmp;
            else answer-=tmp;
        }
        System.out.println(answer);
    }

    private long solve(final int bf, final int cnt, final long mult) {
        if (cnt == 0) {
            return m/mult;
        }

        long result = 0l;
        for (int i = bf+1; i <= n-cnt; i++) {
            result += solve(i, cnt-1, mult*arr[i]);
        }
        return result;
    }
}