두 개의 숫자 n과 k가 주어졌다고 가정해 봅시다. 콘테스트에는 총 n명의 학생이 참가하며, 이들 중 일부는 기념품을 받고, 일부는 상장을 받으며, 나머지는 아무것도 받지 못합니다. 무언가를 받은 참가자를 '승자'라고 부릅니다.
다만 기념품과 상장의 수를 정하는 데는 몇 가지 규칙이 있습니다.
- 상장의 수는 반드시 기념품 수의 정확히 k배여야 합니다.
- 승자의 총 수는 n/2를 초과할 수 없습니다.
- 승자가 한 명도 없어도 괜찮습니다.
이러한 규칙에 따라 가능한 최대 승자 수를 구한 뒤, 그때 기념품을 받은 학생 수, 상장을 받은 학생 수, 그리고 승자가 아닌 학생 수를 차례로 출력해야 합니다.
예를 들어 입력이 n = 18, k = 2라면 출력은 [3, 6, 9]가 됩니다. 즉, 기념품을 받은 학생은 3명, 상장을 받은 학생은 6명(3 × 2), 승자가 아닌 학생은 9명입니다.
해결 접근 방식
이 문제는 간단한 산술 계산만으로 해결할 수 있습니다. 승자의 최대 수는 n/2이므로, 기념품 x개와 상장 k×x개를 합한 값이 n/2를 넘지 않아야 합니다. 따라서 다음 공식을 적용합니다.
x := (n / 2) / (1 + k) return x, (k * x), (n - (x + (k * x)))
즉, n/2를 (1 + k)로 나눈 몫이 기념품의 최대 개수 x가 되고, 상장은 k×x개, 나머지 학생은 승자가 되지 못합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int k){
int x = (n / 2) / (1 + k);
cout << x << ", " << (k * x) << ", " << (n - (x + (k * x)));
}
int main(){
int n = 18;
int k = 2;
solve(n, k);
}입력
n = 18, k = 2
출력
3, 6, 9