19939번: 박 터뜨리기
$N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을
www.acmicpc.net
문제 설명
K개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.
우리는 게임을 준비하기 위해서, N개의 공을 K개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, N개의 공을 K개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.
게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.
공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.
- N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.
- 각 바구니에는 1개 이상의 공이 들어 있어야 한다.
- 각 바구니에 담긴 공의 개수는 모두 달라야 한다.
- 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.
위의 규칙을 모두 만족하며 N개의 공을 K개의 바구니에 나눠 담을 때, 나눠 담을 수 있는지 여부를 결정하고, 담을 수 있는 경우에는 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 계산해서 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 공의 개수를 나타내는 N과 팀의 수를 나타내는 정수 K가 주어진다.
출력
N개의 공을 K개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 출력한다.
제한
- 시간 제한 0.25초
- 메모리 제한 512 MB
풀이
#include <iostream>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
int ans = 0;
int nn[1001];
for (int i = 1; i <= k; i++)
{
ans += i;
}
n -= ans;
if (n < 0)
{
cout<<"-1";
}
else
{
nn[0] = n / k;
n -= (n / k) * k;
for (int i = 1; i <= k; i++)
{
nn[i] = nn[i - 1] + 1;
}
if(n != 0)
nn[k]++;
cout << nn[k] - nn[1];
}
}1부터 K까지 최소로 공을 넣게 되는 경우 몇개의 공이 필요한지 먼저 계산을 했다.
이때 N의 값을 초과한다면 -1을 출력하고 그렇지 않은 경우 그만큼 N의 값에서 빼서 남은 공의 수를 계산했다.
K개의 바구니에 공을 하나씩 넣게되면 전체 공의 수가 K만큼 감소하게 된다.
이를 이용해서 남은 공에서 K만큼 나누게 되면 전체 바구니에 K만큼 공이 들어가게 되고 그 값이 첫번째 바구니에 들어가야할 공의 수가 된다.
나누어 떨어지지 않는 경우 남은 공의 수를 계산해서 바구니에 넣어주어야 한다.
바구니의 뒤에서부터 공을 하나씩 넣어주면 모두 다른 수의 공을 넣을 수 있고 남은 공도 처리할 수 있다.
마지막 바구니의 값만 있으면 되기 때문에 마지막 갑만 증가시키고 값의 차이를 계산해 출력한다.
'Backjoon' 카테고리의 다른 글
| [BOJ][C++] 1925 - 삼각형 (0) | 2023.01.19 |
|---|---|
| [BOJ][C++] 2638 - 치즈 (0) | 2022.12.20 |
| [BOJ][C++] 3987 - 보이저 1호 (0) | 2022.10.14 |
| [BOJ][C++] 1477 - 휴게소 세우기 (1) | 2022.10.13 |
| [BOJ][C++] 1303 - 전쟁 - 전투 (0) | 2022.10.06 |
