두 정수 N과 K가 주어졌다고 가정해 보겠습니다. 우리의 목표는 N개의 크래커를 K명의 사용자에게 최대한 공평하게 분배하는 것입니다. 이때, 한 명의 사용자가 받는 크래커 개수 중 최댓값과 최솟값 사이의 차이를 가능한 한 작게 만들어야 하며, 그 차이의 최솟값을 구해야 합니다.
문제 예시
예를 들어 N = 7, K = 3이라고 입력되면 출력은 1이 됩니다. 세 명의 사용자가 각각 2개, 2개, 3개의 크래커를 받았을 때, 가장 많이 받은 개수(3개)와 가장 적게 받은 개수(2개)의 차이가 1이 되기 때문입니다.
접근 방법
이 문제는 아주 간단한 수학적 관찰 하나로 해결할 수 있습니다.
- N이 K로 나누어떨어지는 경우: 모든 사용자가 정확히 N ÷ K개씩 받을 수 있으므로 차이는 0입니다.
- N이 K로 나누어떨어지지 않는 경우: 일부 사용자는 ⌊N/K⌋개를, 나머지 사용자는 ⌈N/K⌉개를 받게 되므로 차이는 반드시 1이 됩니다.
따라서 다음과 같은 단계로 풀이할 수 있습니다.
만약 n mod k == 0이라면:
return 0
그렇지 않다면:
return 1
구현 예제
아래 C++ 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int k){
if (n % k == 0){
return 0;
} else{
return 1;
}
}
int main(){
int N = 7;
int K = 3;
cout << solve(N, K) << endl;
}
입력
7, 3
출력
1
복잡도 분석
이 알고리즘은 나머지 연산을 딱 한 번만 수행하면 되므로 시간 복잡도는 O(1)이며, 추가 메모리도 필요하지 않아 공간 복잡도 역시 O(1)입니다. 즉, 어떤 입력 크기에 대해서도 즉시 답을 계산할 수 있는 매우 효율적인 풀이입니다.