두 개의 숫자 A와 B가 주어지고, 숫자의 범위를 정의하는 START와 END 값도 함께 제공됩니다. 여기서 A번째 타일에는 흰색 페인트가, B번째 타일에는 검은색 페인트가 칠해져 있다고 가정합니다. 만약 어떤 타일에 흰색과 검은색이 모두 칠해져 있다면 그 타일은 회색(grey)이 됩니다. 우리의 목표는 이러한 회색 타일의 총 개수를 구하는 것입니다.
이 문제는 START부터 END까지의 숫자를 하나씩 순회하면서, 각 숫자가 A와 B 양쪽 모두의 배수인지 확인하는 방식으로 해결할 수 있습니다. 조건을 만족하면 카운트를 증가시키면 됩니다.
예제로 이해하기
입력 예제 1
START=10 END=20 A=3 B=6
출력:
A와 B의 공배수 (회색 타일): 2
설명: 범위 내에서 12와 18이 3과 6의 공배수에 해당합니다.
입력 예제 2
START=1 END=100 A=10 B=11
출력:
A와 B의 공배수 (회색 타일): 0
설명: 1부터 100 사이에는 10과 11의 공배수가 존재하지 않습니다. (최소공배수는 110이므로)
접근 방법
범위를 나타내는 정수 START와 END를 입력받습니다.
두 개의 변수 A와 B를 입력받습니다.
함수 countGrey(int start, int end, int a, int b)는 범위와 a, b 값을 받아 해당 범위 내에서 a와 b의 공배수 개수를 반환합니다.
공배수를 세기 위한 초기 변수 count를 0으로 설정합니다.
for 반복문을 사용하여 i=start부터 i=end까지 범위의 숫자를 순회합니다.
i%a==0 && i%b==0 조건을 만족하면 'i'는 a와 b 양쪽 모두의 배수, 즉 회색 타일입니다.
모든 반복이 끝나면 count에는 a와 b의 공배수 총 개수가 저장됩니다.
count를 결과값으로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int countGrey(int start, int end, int a, int b){
int count = 0;
for (int i = start; i <= end; i++){
if(i%a==0 && i%b==0) // 회색 타일인 경우
{ count++; }
}
return count;
}
int main(){
int START =10, END = 30;
int A=4, B=3;
cout <<"A와 B의 공배수 (회색 타일): "<<
countGrey(START,END, A, B);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
A와 B의 공배수 (회색 타일): 2
이 예제에서는 4와 3의 최소공배수인 12와 24가 10~30 범위 내에 존재하므로 결과는 2가 됩니다.
성능 개선 팁
범위가 매우 넓은 경우 단순 순회 방식은 비효율적일 수 있습니다. 이때는 최소공배수(LCM)를 활용하면 더 효율적으로 계산할 수 있습니다. LCM(A, B) = (A × B) / GCD(A, B) 공식으로 최소공배수를 구한 뒤, 범위 내 LCM의 배수 개수만 계산하면 O(1) 시간 복잡도로 문제를 해결할 수 있습니다.