C++로 n보다 크면서 k로 나누어 떨어지는 가장 작은 정수 구하기

두 개의 숫자 n과 k가 주어졌을 때, n보다 크면서 k로 나누어 떨어지는 가장 작은 정수 x를 구하는 문제입니다.

예를 들어 n = 5, k = 3이 입력으로 주어진다면, 5보다 크면서 3으로 나누어 떨어지는 가장 작은 수는 6이므로 출력 결과는 6이 됩니다.

해결 방법

이 문제는 복잡한 반복문 없이 간단한 수식 하나로 해결할 수 있습니다.

return n + k - (n mod k)

이 공식의 동작 원리는 다음과 같습니다.

• n % k는 n을 k로 나눈 나머지를 의미합니다.
• k - (n % k)는 n에서 다음 배수까지 남은 거리를 나타냅니다.
• 따라서 n + k - (n % k)를 계산하면 n보다 큰 k의 가장 가까운 배수가 됩니다.

만약 n이 이미 k로 나누어 떨어진다면 나머지가 0이 되어 결과는 n + k가 되는데, 이는 'n보다 큰' 조건을 만족하는 올바른 값입니다.

구현 예제

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(int n, int k){
    return n + k - n % k;
}
int main(){
    int n = 5;
    int k = 3;
    cout << solve(n, k) << endl;
}

입력

5, 3

출력

6

이처럼 나머지 연산자(%)를 활용한 한 줄 수식만으로도 O(1) 시간 복잡도에 문제를 해결할 수 있어 매우 효율적입니다.