Codeforces Round #711 (Div. 2) A, B

A. GCD Sum

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        ll n;
        cin >> n;
        while(true){
            string s = to_string(n);
            ll sum = 0;
            for(char x : s){
                sum += (ll)x-'0';
            }
            if(gcd(n, sum) > 1) break;
            n++;
        }
        cout << n << "\n";
    }
    return 0;
}

주어진 수 n과 n의 자리수를 모두 더한 값의 최대공약수가 1보다 크도록 n을 1씩 증가시킬 때 제일 작은 값을 구하는 문제이다.

문제의 조건을 그대로 구현해주면 된다.

B. Box Fitting

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n, W;
        cin >> n >> W;
        map<int, int> w;
        for(int i = 0; i < n; i++){
            int tmp;
            cin >> tmp;
            w[tmp]++;
        }
        int ans = 0;
        while(n){
            ans++;
            int rW = W;
            for(int x = 19; x >= 0; x--){
                int v = pow(2, x);
                int d = rW/v;
                int c = w[v];
                int e = min(d, c);
                rW -= v*e;
                w[v] -= e;
                n -= e;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

너비가 2의 거듭제곱 형태로 주어지는 n개의 높이 1 직사각형 블록을 W 너비의 박스에 담을 때 가능한 높이의 최소값을 구하는 문제이다.

예제 몇개를 풀다보니 너비가 큰 블록부터 가능한대로 쌓아 올리는것이 최적해일 것 같아 그리디로 해결했다.

후기

1솔 전사를 탈출했다. C번은 바텀업 dp 연습이 부족해서 풀지 못했다.