문제

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

댓글