C++로 L부터 R까지 범위 내 홀수·짝수 개수 구하기

문제 소개

정수 값으로 이루어진 L부터 R까지의 범위가 주어졌을 때, 해당 범위 안에 포함된 짝수와 홀수의 개수를 각각 계산하는 것이 목표입니다.

입력 − L = 7, R = 17

출력 − L부터 R까지 범위의 짝수 개수: 5
L부터 R까지 범위의 홀수 개수: 6

입력 − L = 1, R = 10

출력 − L부터 R까지 범위의 짝수 개수: 5
L부터 R까지 범위의 홀수 개수: 5

적용한 접근 방식

• L부터 R까지의 범위를 입력받습니다.

• L과 R 값을 함수에 전달해 짝수 개수를 먼저 구하고, 그 반환값을 이용해 홀수 개수를 계산합니다.

• i를 L부터 R까지 1씩 증가시키며 반복하는 FOR 루프를 시작합니다.

• 루프 안에서 i % 2 == 0 조건을 만족하면(즉, i가 짝수이면) 짝수 카운트(even)를 1 증가시킵니다.

• 반복이 끝나면 짝수 개수를 반환합니다.

• 홀수 개수는 범위 내 전체 숫자 개수에서 짝수 개수를 뺀 값, 즉 odd = (R − L + 1) − even으로 구합니다. 어떤 정수는 반드시 홀수 아니면 짝수이기 때문입니다.

예제 코드

#include <iostream>
using namespace std;
int Odd_Even(int L, int R){
    int even = 0;
    for(int i = L; i <= R; i++){
        if(i % 2 == 0){
            even++;
        }
    }
    return even;
}
int main(){
    int L = 7, R = 17;
    int even = Odd_Even(L, R);
    int odd = (R - L + 1) - even;
    cout<<"Count of Even numbers in a range from L to R are: "<<even<<endl;
    cout<<"Count of Odd numbers in a range from L to R are: "<<odd;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

Count of Even numbers in a range from L to R are: 5
Count of Odd numbers in a range from L to R are: 6

개선: O(1) 수학 공식으로 더 빠르게 계산하기

위 방법은 범위의 크기만큼 반복하므로 시간 복잡도가 O(N)입니다. 하지만 수학 공식을 사용하면 반복문 없이 O(1)에 즉시 계산할 수 있습니다.

범위 [L, R]에 포함된 짝수의 개수는 아래 공식으로 구할 수 있습니다(정수 나눗셈 기준).

짝수 개수 = R / 2 − (L − 1) / 2
홀수 개수 = (R − L + 1) − 짝수 개수

예를 들어 L = 1, R = 10이라면 짝수 개수는 10 / 2 − 0 / 2 = 5, 홀수 개수는 10 − 5 = 5가 되어 앞선 실행 결과와 일치합니다. 범위가 매우 넓은 경우(예: 최대 10억)에도 이 공식을 사용하면 즉시 답을 얻을 수 있다는 점이 큰 장점입니다.