Algorithm/코딜리티

(코딜리티) Lesson 5 : CountDiv - Python

casim 2021. 1. 19. 22:07

문제 : app.codility.com/programmers/lessons/5-prefix_sums/

 

5. Prefix Sums lesson - Learn to Code - Codility

Compute number of integers divisible by k in range [a..b].

app.codility.com

문제 설명

3개의 정수인 A, B, K가 주어질 때, A와 B사에 K로 나누어떨어지는 갯수를 구하시오.

 

예를 들어,

A = 6, B = 11, K = 2 일때,

6, 8, 10이므로 3을 return한다.

제한 사항

A와 B는 0~2,000,000,000사이의 값

K는 1~2,000,000,000사이의 값

A <= B

코드

def solution(A, B, K):
    
    a = (A-1)//K
    b = B//K
    c = b-a

    return c

해설

보통 1~N까지 N을 K로 나누면 나오는 몫이 K로 나눌때 딱 떨어지는 갯수입니다.

그렇다면 이경우는 1~B까지 나눈 몫에 1~(A-1) 나눈 몫을 빼줍니다.

A-1같은 경우는 A에서 B까지 사이의 갯수를 구할 때, A도 포함하기 때문에 A-1로 값을 구합니다.