문제 개요
이 튜토리얼에서는 N보다 작거나 같은 수 중에서 K로 나누어 떨어지는 가장 큰 수를 찾는 프로그램을 C++로 작성해 보겠습니다.
예를 들어, N이 33이고 K가 5라면, 5로 나누어 떨어지면서 33 이하인 가장 큰 수는 30입니다.
해결 방법
문제를 해결하는 단계는 다음과 같습니다.
- 두 정수 n과 k를 초기화합니다.
- 나머지 연산자(%)를 사용하여 n을 k로 나눈 나머지를 구합니다.
- 나머지가 0이라면 n 자체가 k의 배수이므로 n을 그대로 반환합니다.
- 나머지가 0이 아니라면 n에서 나머지를 뺀 값을 반환합니다.
이 방법이 작동하는 원리는 간단합니다. n에서 n % k를 빼면 결과값은 항상 k의 배수가 되고, 그 값은 n보다 작거나 같습니다. 따라서 주어진 조건을 만족하는 가장 큰 수가 됩니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int findLargerNumber(int n, int k) {
int remainder = n % k;
if (remainder == 0) {
return n;
}
return n - remainder;
}
int main() {
int n = 33, k = 5;
cout << findLargerNumber(n, k) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
30
n이 33이고 k가 5일 때, 나머지는 33 % 5 = 3이므로 33 - 3 = 30이 반환되는 것을 확인할 수 있습니다.
마무리
이번 튜토리얼에서는 나머지 연산자 하나만으로 N 이하에서 K로 나누어 떨어지는 가장 큰 수를 O(1) 시간 복잡도로 구하는 방법을 알아보았습니다. 반복문 없이 단순한 산술 연산으로 해결할 수 있어 매우 효율적인 기법입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.