격자 상태 탐색 및 비트마스크 활용

첫 번째 문제는 주어진 격자에서 특정 행과 열을 선택하여 제거했을 때, 남아있는 검은색 셀의 개수가 정확히 K 가 되는 경우의 수를 찾는 문제이다. 행과 열의 개수가 작으므로 비트마스크를 이용하여 모든 조합을 탐색하는 방식이 적합하다.

각 행과 열에 대해 선택 여부를 비트로 표현하여 반복문을 구성한다. 선택된 행이나 열에 포함된 검은색 셀은 제거된 것으로 간주하며, 최종적으로 제거된 셀의 개수가 전체 검은색 셀에서 K 를 뺀 값과 일치하는지 확인한다.

#include <iostream>
#include <vector>
using namespace std;

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

    int R, C, K;
    if (!(cin >> R >> C >> K)) return 0;

    vector<string> grid(R);
    int totalBlack = 0;

    for (int i = 0; i < R; ++i) {
        cin >> grid[i];
        for (char c : grid[i]) {
            if (c == '#') totalBlack++;
        }
    }

    int validCases = 0;
    int targetRemove = totalBlack - K;

    for (int rowMask = 0; rowMask < (1 << R); ++rowMask) {
        for (int colMask = 0; colMask < (1 << C); ++colMask) {
            int removedCount = 0;
            for (int r = 0; r < R; ++r) {
                for (int c = 0; c < C; ++c) {
                    bool isRemoved = (rowMask & (1 << r)) || (colMask & (1 << c));
                    if (isRemoved && grid[r][c] == '#') {
                        removedCount++;
                    }
                }
            }
            if (removedCount == targetRemove) {
                validCases++;
            }
        }
    }

    cout << validCases << endl;
    return 0;
}

순열 그래프에서의 사이클 탐지 및 최대 점수 계산

두 번째 문제는 각 정점이 하나의 나가는 간선을 가진 그래프 구조에서, 시작점으로부터 K 번 이동했을 때 얻을 수 있는 최대 점수 합을 구하는 문제이다. 이러한 구조는 기능적 그래프 (Functional Graph) 로 불리며, 반드시 사이클을 포함하게 된다.

각 시작 정점마다 경로를 따라가며 사이클을 발견하고, 사이클 구간의 점수 합과 순서를 기록한다. K 번 이동 중에서 사이클을 몇 바퀴 도는지와 나머지를 계산하여 그리디하게 최대 값을 도출한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 200005;
int nxt[MAXN];
int score[MAXN];
int visited[MAXN];
long long prefixSum[MAXN];
vector<int> cyclePath;

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

    int n;
    long long k;
    cin >> n >> k;

    for (int i = 1; i <= n; ++i) cin >> nxt[i];
    for (int i = 1; i <= n; ++i) cin >> score[i];

    long long globalMax = -1e18;

    for (int start = 1; start <= n; ++start) {
        memset(visited, 0, sizeof(visited));
        cyclePath.clear();
        long long currentSum = 0;
        int curr = start;

        while (!visited[curr]) {
            visited[curr] = 1;
            curr = nxt[curr];
            currentSum += score[curr];
            cyclePath.push_back(score[curr]);
        }

        int len = cyclePath.size();
        long long cycleTotal = currentSum;
        long long currentVal = 0;

        if (cycleTotal > 0) {
            long long rounds = k / len;
            int remainder = k % len;
            if (remainder == 0) {
                rounds--;
                remainder = len;
            }
            currentVal = rounds * cycleTotal;
            for (int i = 0; i < remainder; ++i) {
                currentVal += cyclePath[i];
                globalMax = max(globalMax, currentVal);
            }
        } else {
            if (k < len) {
                for (int i = 0; i < k; ++i) {
                    currentVal += cyclePath[i];
                    globalMax = max(globalMax, currentVal);
                }
            } else {
                for (int i = 0; i < len; ++i) {
                    currentVal += cyclePath[i];
                    globalMax = max(globalMax, currentVal);
                }
            }
        }
    }

    cout << globalMax << endl;
    return 0;
}

약수 개수 기반 합계 산출 최적화

세 번째 문제는 1 부터 N 까지 각 정수의 약수 개수를 구하고, 이를 해당 정수와 곱한 값의 총합을 계산하는 문제이다. 각 숫자마다 약수를 찾는 방식은 시간 복잡도가 높으므로, 에라토스테네스의 체와 유사한 접근법을 사용한다.

잠재적인 약수 i 를 기준으로 하여 i 의 배수들에 대해 약수 개수를 누적한다. 이렇게 하면 모든 숫자에 대한 약수 개수를 효율적으로 카운팅할 수 있으며, 최종적으로 각 숫자와 그 약수 개수의 곱을 합산한다.

#include <iostream>
#include <vector>
using namespace std;

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

    int limit;
    cin >> limit;

    vector<int> divisorCount(limit + 1, 0);

    for (int i = 1; i <= limit; ++i) {
        for (int j = i; j <= limit; j += i) {
            divisorCount[j]++;
        }
    }

    unsigned long long totalSum = 0;
    for (int i = 1; i <= limit; ++i) {
        totalSum += (unsigned long long)divisorCount[i] * i;
    }

    cout << totalSum << endl;
    return 0;
}