문제
https://codeforces.com/problemset/problem/1476/A
걸린 시간
01 : 00 : 21
풀이
C++
#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin >> tc;
while(tc--){
int n, k;
cin >> n >> k;
int s = ceil((float)n/k)*k;
int m = s/n;
int i = (m+1)*n-s;
if(n-i == 0) cout << m << "\n";
else cout << m+1 << "\n";
}
return 0;
}
n개의 원소 a1, ..., an 의 합을 s
라고 할 때 k로 나누어 떨어지는, 즉 k 의 배수 중 가능한 제일 작은 값을 s
로 한다. s
를 구성하는 다양한 경우 중 원소 a 의 최대값을 구하여야 한다.
작은 예제들로부터 s
/ "남은 자리의 개수" 의 몫을 s
에서 줄여나가며 반복하는것이 최적해라는걸 알아냈다. 하지만 이 방법은 시간이 너무 걸린다. 많은 고민끝에 처음 구했던 몫에서 1증가하는 지점(최대값)을 이용한 방법을 떠올려냈다.
'Codeforces' 카테고리의 다른 글
Codeforces Round #710 (Div. 3) A, C (0) | 2021.03.27 |
---|---|
Codeforces #1476B Inflation (0) | 2021.03.24 |
Codeforces #1480B The Great Hero (0) | 2021.03.22 |
Educational Codeforces Round 106 (Rated for Div. 2) A (0) | 2021.03.19 |
Codeforces Round #708 (Div. 2) A (0) | 2021.03.19 |
댓글