Created by potrace 1.14, written by Peter Selinger 2001-2017 ARC

1441) 나누어 질까

 
  • 2022년 02월 10일

1441

제목 : 나누어 질까

  • 어떤 숫자 배열 A가 주어지면, L보다 크거나 같고, R보다 작거나 같은 자연수 중에, A에 속해있는 원소 중 적어도 하나로 나누어지는 수의 개수를 구하는 프로그램을 작성하시오.

  • 입력 : 첫째 줄에 A의 크기 N과 L, R이 주어진다. N은 18보다 작거나 같은 자연수이고, L은 1,000,000,000보다 작거나 같은 자연수, R은 L보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 둘째 줄에 A에 속하는 원소가 들어온다. 각 원소는 공백을 사이에 두고 구분되어 있고, 원소는 1,000,000,000보다 작거나 같은 자연수이다.
  • 출력 : 첫째 줄에 L보다 크거나 같고, R보다 작거나 같은 자연수 중에, A에 속해있는 원소 중 적어도 하나로 나누어지는 수의 개수를 출력한다.

문제를 보기만 해도 어지럽다. 글이 짧으면 짧을수록 어려운건 고등학교 수리시절부터 내려오는 유구한 전통같은 것인가보다. 스터디에서 코드업에서 풀라고 내준 문제였는데 멍청하게도 백준에서 푸는 바람에 난이도가 천배쯤 어려운 이 문제를 풀게 되었다.

문제 자체는 간단하다. L<= x <= R을 만족하는 x 중, 배열 A의 원소들의 배수들의 갯수를 세는 문제이다. 예를들어 L=12<= x<= R= 16 이고 A=[3,7] 일 때, 위 조건을 만족하는 수는 12, 14, 15 이므로 답은 3이 된다. 뭐야 엄청 간단하잖아? x를 A의 원소들로 나눠서 나머지가 있으면 패스하고 모두 나머지가 0인 경우만 세서 출력하면 되겠다! 라고 생각했다면 <입력>란을 다시보자.

A의 원소 갯수가 18개보다 작거나 같음에도 불구하고 L과 R의 크기가 어지러울 정도로 크기 때문에 for문으로 돌렸다가는 절대 시간안에 해결하지 못한다. 그렇다면 하나하나 세지 않고 문제를 풀어야 하는데… 아이디어는 이렇다. 예를 들어 1 ~ 8 의 정수들에 대해 생각해보자. A=[2, 3] 일 때, 조건을 만족하는 수는 2, 3, 4, 6, 8로 정답은 5이다. 그런데 이 중에는 2의 배수(2,4,6,8)도 있고 3의 배수(3, 6)도 있으며, 2와 3의 공배수(6)도 있다. 뭔가 느낌이 오는가? n(2) + n(3)- n(6) = n({2,3,4,6,8}) = 5 이다. 즉 어떤 두 수의 배수들의 갯수는 각 수의 배수들의 갯수(ex.n(2)+n(3)) 에서 두 수의 최소 공배수의 배수(ex. n(6)) 만큼 빼주면 된다.

그렇다면 임의 N개 만큼 원소를 갖고 있는 A의 경우는 어떨까? 중학교 때 배운 벤다이어그램을 생각하면 된다. 중복해서 세어준걸 빼고, 다시 중복해서 뺀걸 더하는 걸 반복하면 된다. 예를 들어 3개의 수 2,3,7의 배수 갯수를 센다고 하면 n(2) + n(3) + n(7) - n(6) - n(21) - n(14) + n(42) 가 된다. 4 개라면? 마찬가지로 1개 씩 뽑았을 때 +, 두 개씩 뽑아서 최소공배수(=LCM)를 만들면 - … 를 하면된다.

지금까지 알고리즘 공부하면서 알아놓은 것들을 정말 알차게사용했다. 먼저 1) 최소공배수를 구하는 알고리즘, 2) 조합을 이용한 최소공배수의 대상 되는 숫자 뽑기. 이 두 개를 활용하면 아주 깔끔하게 풀린다. 물론 조합을 구현하는게 쉽지 않기 때문에 나는 양심없이 파이썬의 itertools를 활용해서 해결하였다.

코드는 다음과 같다.

import sys
from itertools import combinations

n, l, r = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

def gcd(x, y):#최대공약수
   while y:
       x, y = y, x % y
   return x

def lcm(x, y):#최소공배수
   return x * y // gcd(x,y)

sums = 0
for i in range(n):
    sums += r//a[i] - l//a[i] + (not l%a[i])

for i in range(2, n+1):# 벤다이어그램 생각하기
    comb = list(combinations(a, i))#i개 만큼 A로부터 뽑아서 최소공배수를 구하기
    temp = 0
    for c in comb:
        divider = lcm(c[0], c[1])#한 번에 여러개의 공배수를 못구하니까 일단 1, 2번 숫자로 만들고
        for j in range(i-2):
            divider = lcm(divider, c[j+2])# 그 이후에 하나씩 (공배수, A의 원소)의 공배수를 구하자
        temp += r//divider - l//divider#(1~r 까지 배수) - (1~l까지 배수)
        temp += (not l%divider)# 만약 l이 최소공배수의 배수라면 그것도 포함해야하므로 나머지가 1인 경우 더해주자.
    if i%2:#홀 수 번째 조합들의 경우(숫자를 홀수개 뽑아서 공배수를 계산한 경우)
        sums += temp#(전체 갯수에 더하기)
    else:
        sums -= temp#숫자를 짝수개 뽑은 경우 전체갯수에서 빼주자!
print(sums)

자력으로 플래티넘 문제를 풀다니… 이건 지금껏 해온 공부의 힘일까 아니면 착각의 힘일까.

검색