Lesson 5. Perfix Sums - CountDiv #2 (속도 개선)

1. 속도 개선 아이디어

0부터 B까지의 정수들 중에서, K로 나누어 떨어지는 수는 몇 개일까?  (B \( \div \) K)개

 

그렇다면 \( 0 \leq A \leq B \) 일 때, [A..B]구간에서 K로 나누어 떨어지는 수는 몇 개일까?

0에서 B까지의 범위에서 K로 나누어 떨어지는 수: (B \( \div \) K)

0에서 A까지의 범위에서 K로 나누어 떨어지는 수: (A \( \div \) K)

[A..B]구간에서 K로 나누어 떨어지는 수: (B \( \div \) K) \( - \) (A \( \div \) K) 

 

2. 코드 (C++)

int solution(int A, int B, int K) {

    int cnt = (B/K) - (A/K); // (A % K == 0) 도 포함해서 뺀다.
    if(A % K == 0) cnt++; // 따라서 A가 K로 나누어 떨어지면, 더해줘야한다.
    return cnt;
}

 

 

3. 결과