A - skill

문제는 단순한 조회 표를 기반으로 점수를 반환하는 작업이다. 각 문제 유형별로 하위 점수가 주어지며, 입력된 번호에 따라 해당 점수를 출력하면 된다. 2차원 배열 사용 시 컴파일 오류나 런타임 오류가 발생할 수 있어, 안정성을 위해 4개의 일차원 배열을 별도로 선언하여 처리했다.

#include <bits/stdc++.h>
using namespace std;

int a1[] = {0, 20, 20, 20, 20, 20};
int a2[] = {0, 20, 20, 10, 30, 20};
int a3[] = {0, 25, 25, 30, 20};
int a4[] = {0, 15, 15, 15, 10, 10, 15, 20};

int main() {
    int n, m;
    cin >> n >> m;
    if (n == 1) cout << a1[m] << '\n';
    if (n == 2) cout << a2[m] << '\n';
    if (n == 3) cout << a3[m] << '\n';
    if (n == 4) cout << a4[m] << '\n';
    return 0;
}

B - leg

좌표 (1,1)에서 (n,m)까지 이동할 때, 네 가지 연산 (x+1,y), (x,y+1), (x+1,y+1) 등이 있으며, 각각 비용이 다르다. 핵심은 두 대각선 이동 방식인 (a+d)와 (b+c) 중 더 저렴한 것을 최대한 활용하는 것이다. 먼저 min(a+d, b+c)를 이용해 (x,x) 형태로 가능한 만큼 이동한 후, 남은 거리는 각각 수직 또는 수평 방향으로 이동하며 추가 비용을 계산한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll n, m, a, b, c, d;
    cin >> n >> m >> a >> b >> c >> d;
    ll base = min(a + d, b + c);
    ll steps = min(n, m);
    ll cost = steps * base;

    if (n < m) {
        ll rem = m - n;
        cost += (rem + 1) / 2 * b + rem / 2 * d;
    } else {
        ll rem = n - m;
        cost += (rem + 1) / 2 * a + rem / 2 * c;
    }
    cout << cost << '\n';
    return 0;
}

C - calculate

임의 진법에서 두 수 A와 B의 곱셈을 수행하되, 각 자리마다 진법이 다르다. 중요한 제약 조건은 B의 자릿수가 최대 10자리라는 점이다. 즉, B는 정수형 변수로 완전히 표현 가능하다. 따라서 B를 일반 정수로 변환한 후, A를 고정점수 형식으로 저장하고 각 자리마다 곱셈을 수행하며 자리올림 처리를 진행하면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
ll p[N], a[N], res[N];
string A, B;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];
    cin >> A >> B;

    reverse(A.begin(), A.end());
    for (int i = 0; i < A.size(); i++)
        a[i] = A[i] - '0';

    ll valB = 0;
    for (char c : B)
        valB = valB * 10 + (c - '0');

    for (int i = 0; i < n; i++) {
        res[i] += a[i] * valB;
        if (res[i] >= p[i]) {
            res[i + 1] += res[i] / p[i];
            res[i] %= p[i];
        }
    }

    int hi = n - 1;
    while (hi > 0 && !res[hi]) hi--;
    for (int i = hi; i >= 0; i--) cout << res[i];
    cout << '\n';
    return 0;
}

D - friends

배열을 여러 구간으로 나누되, 각 구간의 합이 모두 동일한 값 L이 되도록 하고자 한다. 이때 L은 전체 합 S의 약수여야 하므로, 가능한 후보는 S의 모든 약수로 제한된다. 각 접두사 합 s_i에 대해 gcd(s_i, S)는 어떤 약수 L의 배수일 경우 기여하게 된다. 따라서 각 접두사에 대해 g = gcd(s_i, S)를 구하고, 이 값이 포함하는 모든 약수에 카운트를 더한다. 이후 각 길이 k에 대해 최대 가능한 L 값을 후행 최댓값으로 갱신한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
ll a[N], cnt[1000], ans[N];
vector<ll> divs;

ll gcd(ll x, ll y) {
    return y ? gcd(y, x % y) : x;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i-1];
    }

    ll sum = a[n];
    for (ll x = 1; x * x <= sum; x++) {
        if (sum % x == 0) {
            divs.push_back(x);
            if (x * x != sum) divs.push_back(sum / x);
        }
    }
    sort(divs.begin(), divs.end());

    unordered_map<ll, int> idx;
    for (int i = 0; i < divs.size(); i++)
        idx[divs[i]] = i;

    for (int i = 1; i <= n; i++) {
        ll g = gcd(a[i], sum);
        if (idx.count(g)) cnt[idx[g]]++;
    }

    for (int i = 0; i < divs.size(); i++) {
        for (int j = i + 1; j < divs.size(); j++) {
            if (divs[j] % divs[i] == 0)
                cnt[i] += cnt[j];
        }
        ans[cnt[i]] = max(ans[cnt[i]], divs[i]);
    }

    for (int i = n; i >= 1; i--)
        ans[i] = max(ans[i], ans[i+1]);

    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << '\n';
    return 0;
}

E - plan

n명의 사람이 있고, 각 사람은 m개의 관심사 중 일부를 가지고 있다. 두 사람이 공통 관심사가 없으면 소통하지 않는다. 최대 k쌍 이하의 비소통 쌍을 포함하는 가장 긴 연속 구간을 구해야 한다. m ≤ 10이므로 상태를 비트마스크로 표현할 수 있다. 또한 문제는 구간이 늘어날수록 비소통 쌍의 수가 증가하는 단조성을 가지므로 투 포인터 기법을 적용할 수 있다. 투 포인터를 사용하면서 현재 구간 내 각 상태별 인원 수를 유지하고, 새로운 사람을 추가할 때 그 사람과 비소통 가능한 모든 상태의 인원 수를 더해 누적한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 5;
const int MAX_MASK = 1 << 11;

ll cnt[MAX_MASK];
int hobby[MAX_N];

ll countNonCommunicable(int mask, int m) {
    ll total = 0;
    for (int state = 0; state < (1 << m); state++) {
        if ((state & mask) == 0)
            total += cnt[state];
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    m++; // 실제 입력은 1~m까지

    for (int i = 1; i <= n; i++) {
        int num;
        cin >> num;
        for (int j = 0; j < num; j++) {
            int h;
            cin >> h;
            hobby[i] |= (1 << h);
        }
    }

    ll nonComm = 0;
    int left = 1;
    ll maxLen = 0;

    for (int right = 1; right <= n; right++) {
        nonComm += countNonCommunicable(hobby[right], m);
        cnt[hobby[right]]++;

        while (nonComm >= k) {
            cnt[hobby[left]]--;
            nonComm -= countNonCommunicable(hobby[left], m);
            left++;
        }
        maxLen = max(maxLen, (ll)(right - left + 1));
    }

    cout << maxLen << '\n';
    return 0;
}

총평 및 교훈

• 데이터 범위를 꼼꼼히 확인하라. C번 문제에서 B의 자릿수가 10자리 이하라는 점을 간과했기 때문에 고생했으며, E번에서도 m의 크기가 작아 비트마스크를 충분히 감당할 수 있음에도 불구하고 이를 ‘폭력적인 접근’이라 생각해 배제했다.
• 직관에 너무 의존하지 마라. DP나 복잡한 알고리즘을 먼저 생각하기보다는, 제약 조건에서 힌트를 얻는 것이 중요하다.
• 단순한 해법이 정답일 수 있다. 특히 작은 입력 크기에서는 완전 탐색이나 비트마스크도 효율적인 정해가 될 수 있다.