대회 경향성 분석 및 난이도 평가

2022 년부터 2024 년까지 이어진 전국 본선 모의 훈련 문제들을 종합적으로 분석한 결과, 전반적인 난이도 흐름은 2022 > 2024 > 2023 순으로 예상된다. 출제 패턴을 살펴보면 대부분 초기 문제에 문자열 처리나 시뮬레이션 유형이 등장하며, 이후 완전 탐색, 자료구조 활용, 그래프 이론과 동적 계획법(DP) 결합 형태가 차례로 배치된다. 마지막 문제는 고정된 유형 없이 복잡한 DP 나 고급 시뮬레이션이 나타날 가능성이 있다.

---

2024 년 국선전 문제집 해설

문제 1: 부정행위 탐지 (난이도 하)

주어진 입력 스트림 내에서 알파벳과 숫자로 구성된 키워드를 추출하고, 해당 문자의 종류 조합에 따라 가중치를 계산하여 총점, 전체 길이, 단어 수를 출력하는 시뮬레이션 문제다.

접근 방식: 입력된 문자열을 토큰 단위로 분해하거나 정해진 구분자를 기준으로 파싱한다. 연속된 영문자와 숫자만 포함하는 구간을 식별하고, 대소문자 및 숫자의 유무를 체크하여 점수 규칙을 적용한다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void processInput() {
    string token;
    int totalSuspicion = 0;
    int totalLength = 0;
    int wordCount = 0;

    // 빈 문자열이 나올 때까지 읽기
    while (cin >> token) {
        bool hasDigit = false, hasLower = false, hasUpper = false;
        int currentLen = 0;
        string tempWord = "";

        for (char ch : token) {
            if (isdigit(ch)) hasDigit = true;
            else if (islower(ch)) hasLower = true;
            else if (isupper(ch)) hasUpper = true;
            else {
                // 구분자 발견 시 현재 단어 처리
                if (!tempWord.empty()) {
                    if (hasDigit && hasLower && hasUpper) totalSuspicion += 5;
                    else if ((hasLower || hasUpper) && hasDigit) totalSuspicion += 3;
                    else if (hasLower && hasUpper) totalSuspicion += 1;
                    
                    totalLength += (int)tempWord.length();
                    wordCount++;
                }
                // 상태 초기화
                hasDigit = false; hasLower = false; hasUpper = false;
                tempWord.clear();
            }
            // 구분자가 아닌 경우 단어에 추가
            if (isalnum(ch)) tempWord += ch;
        }
        
        // 마지막 단어 처리
        if (!tempWord.empty()) {
            if (hasDigit && hasLower && hasUpper) totalSuspicion += 5;
            else if ((hasLower || hasUpper) && hasDigit) totalSuspicion += 3;
            else if (hasLower && hasUpper) totalSuspicion += 1;
            
            totalLength += (int)tempWord.length();
            wordCount++;
        }
    }

    cout << totalSuspicion << "\n";
    cout << totalLength << " " << wordCount << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    processInput();
    return 0;
}

문제 2: 순위 산출 시스템 II (난이도 하중)

여러 라운드에 걸친 팀들의 랭킹 정보를 받아 최종 누적 점수를 구하고 정렬하여 출력하는 문제다. 랭킹마다 부여되는 점수가 정해져 있으며, 팀별 총점을 기준으로 내림차순 정렬해야 한다.

접근 방식: 랭크에 따른 점수 매핑 테이블을 구성한다. 각 팀의 정보(번호, 현재 점수)를 구조체나 쌍(pair) 으로 관리한다. 모든 입력 라운드가 끝난 후, 유효한 점수를 가진 팀들만 추출하여 지정된 기준 (점수 내림차순, 번호 오름차순) 에 따라 재정렬한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct TeamInfo {
    int id;
    int score;
};

bool compareTeams(const TeamInfo &a, const TeamInfo &b) {
    if (a.score != b.score) return a.score > b.score; // 점수 높은 순
    return a.id < b.id; // 점수 같으면 번호 작은 순
}

void solveRound() {
    int rounds;
    cin >> rounds;
    
    // 랭크별 점수 매핑 (1 위 25 점, 20 위 1 점 등)
    vector<int> rankPoints = {0, 25, 21, 18, 16, 15, 14, 13, 12, 11, 
                              10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    vector<TeamInfo> teams(31, {0, -1}); // 1 인덱스 사용 편의를 위해 크기 31
    
    for (int r = 0; r < rounds; ++r) {
        for (int rank = 1; rank <= 20; ++rank) {
            int teamId, currentRank;
            cin >> teamId >> currentRank;
            
            if (teams[teamId].score == -1) {
                teams[teamId].id = teamId;
            }
            teams[teamId].score += rankPoints[currentRank];
        }
    }

    vector<TeamInfo> activeTeams;
    for (const auto &t : teams) {
        if (t.score != -1) activeTeams.push_back(t);
    }

    sort(activeTeams.begin(), activeTeams.end(), compareTeams);

    for (const auto &t : activeTeams) {
        cout << t.id << " " << t.score << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solveRound();
    return 0;
}

문제 3: 균형 잡힌 그룹 (난이도 중상)

주어진 n 개의 서로 다른 자릿수로 만들 수 있는 모든 n 자리 수들을 생성한 뒤, 이들을 두 그룹으로 나누되 두 그룹의 개수와 제곱수의 합이 각각 같도록 하는 문제를 다룬다.

접근 방식: 먼저 백트래킹 (DFS) 을 통해 모든 가능한 n 자리 수를 생성한다. 다음 단계로 생성된 숫자들의 전체 제곱합을 계산하여 목표 값을 반으로 나눈다. 마지막으로 다시 백트래킹을 수행하여 전체 절반 개수의 숫자를 선택하되 제곱합이 목표 값과 일치하는 경우를 찾는다. 효율성을 위해 가지치기를 적용한다.

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int N;
vector<int> inputs;
vector<long long> generatedNumbers;
long long totalSquareSum = 0;
vector<long long> selectedGroup;
bool foundSolution = false;

// 전치조합 생성
void generatePerms(vector<int>& current, vector<bool>& used) {
    if ((int)current.size() == N) {
        long long num = 0;
        for (int d : current) num = num * 10 + d;
        generatedNumbers.push_back(num);
        return;
    }

    for (int i = 0; i < N; ++i) {
        if (!used[i]) {
            used[i] = true;
            current.push_back(inputs[i]);
            generatePerms(current, used);
            current.pop_back();
            used[i] = false;
        }
    }
}

// 조건 부합하는 부분집합 찾기
void findSubset(int index, int count, long long currentSum) {
    if (foundSolution) return;

    if (count == N / 2) {
        if (currentSum * 2 == totalSquareSum) {
            foundSolution = true;
            for (auto val : selectedGroup) cout << val << "\n";
        }
        return;
    }

    if (index >= generatedNumbers.size()) return;

    // 가지치기: 남은 원소로도 충분한 개수 채우기 불가능한 경우
    if (count + (generatedNumbers.size() - index) < N / 2) return;

    // 포함 시도
    selectedGroup.push_back(generatedNumbers[index]);
    findSubset(index + 1, count + 1, currentSum + generatedNumbers[index] * generatedNumbers[index]);
    if (foundSolution) return;
    selectedGroup.pop_back();

    // 제외 시도
    findSubset(index + 1, count, currentSum);
}

int main() {
    cin >> N;
    inputs.resize(N);
    for (auto &x : inputs) cin >> x;

    vector<int> curPerm;
    vector<bool> visited(N, false);
    generatePerms(curPerm, visited);

    for (long long val : generatedNumbers) {
        totalSquareSum += val * val;
    }

    findSubset(0, 0, 0);

    return 0;
}

문제 4: 도시 이동 경로 최적화 (난이도 상)

도시 간의 이동 비용과 각 도시의 관광 인기 지수를 고려할 때, 출발지에서 도착지까지 이동 비용을 최소화하되 비용이 동일할 경우 경유지의 최대 인기 지수가 최소가 되는 경로를 찾는 문제다.

접근 방식: 다익스트라 알고리즘을 변형하여 사용한다. 일반적인 최단 거리 배열 외에, 해당 거리에 도달했을 때의 최대 열도값을 저장하는 DP 배열을 추가로 관리한다. 간선을 방문할 때 거리가 더 짧거나, 길이가 같지만 열도 조건을 더 잘 만족하면 상태를 갱신한다.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

const long long INF = 1e18;
struct Edge {
    int to;
    int cost;
};

void solveCase() {
    int V, E, Start, Target;
    cin >> V >> E >> Start >> Target;
    
    vector<int> heat(V + 1);
    for (int i = 1; i <= V; ++i) cin >> heat[i];

    vector<vector<Edge>> adj(V + 1);
    for (int i = 0; i < E; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    vector<long long> dist(V + 1, INF);
    vector<int> maxHeat(V + 1, 0);
    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;

    dist[Start] = 0;
    pq.push({0, Start, 0}); 

    while (!pq.empty()) {
        auto [d, u, h] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;
        if (d == dist[u] && h > maxHeat[u]) continue;

        for (auto& edge : adj[u]) {
            long long newDist = d + edge.cost;
            int newH = h;
            
            // 경유지라면 열도 갱신
            if (edge.to != Target) {
                newH = max(h, heat[edge.to]);
            } else {
                newH = h; // 목적지는 열도에 영향 안줌
            }

            if (newDist < dist[edge.to]) {
                dist[edge.to] = newDist;
                maxHeat[edge.to] = newH;
                pq.push({newDist, edge.to, newH});
            } else if (newDist == dist[edge.to]) {
                if (newH < maxHeat[edge.to]) {
                    maxHeat[edge.to] = newH;
                    pq.push({newDist, edge.to, newH});
                }
            }
        }
    }

    if (dist[Target] == INF) cout << "Impossible\n";
    else cout << dist[Target] << " " << maxHeat[Target] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solveCase();
    return 0;
}

문제 5: 그리드 블록 제거 게임 (난이도 상)

격자판에서 가장 큰 합을 가지는 직사각형을 찾아 제거하고, 위의 블록들이 아래로 떨어지게 하는 과정을 반복하여 총점을 구하는 문제다. 삭제 후 공백이 생기면 상단의 요소가 중력에 의해 하강한다.

접근 방식: 브루트 포스로 네 차원의 루프로 모든 직사각형을 검사하거나, 행과 열을 고정하고 일차원 최대 부분합 알고리즘 (Kadane) 을 적용하여 시간 복잡도를 O(N^3) 으로 낮출 수 있다. 문제의 특성상 입력 형식 (열 우선) 과 삭제 후 하강 로직이 핵심이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<vector<int>> grid; // column-major storage based on input

// 하강 로직 시뮬레이션
void gravityDrop() {
    for (int col = 1; col <= N; ++col) {
        vector<int> stableBlock;
        for (int row = 1; row <= N; ++row) {
            if (grid[row][col] != 0) stableBlock.push_back(grid[row][col]);
        }
        for (int row = 1; row <= N; ++row) {
            if (row <= (int)stableBlock.size()) grid[row][col] = stableBlock[row - 1];
            else grid[row][col] = 0;
        }
    }
}

void playGame() {
    cin >> N;
    grid.assign(N + 1, vector<int>(N + 1));
    for (int j = 1; j <= N; ++j) {
        for (int i = 1; i <= N; ++i) {
            cin >> grid[j][i];
            if (grid[j][i] == 0) grid[j][i] = -1e9; // 블랙홀 표시
        }
    }

    int totalScore = 0;
    while (true) {
        // 전구체 계산 생략 (직접 루프 사용 예시)
        int bestVal = -1;
        int bestTLc = -1, bestTLr = -1, bestBRc = -1, bestBRr = -1;

        // O(N^4) 접근 (코드 간결함을 위해 설명용)
        // 실제 제출 시 Kadane 적용 권장
        for (int r1 = 1; r1 <= N; ++r1) {
            for (int r2 = r1; r2 <= N; ++r2) {
                for (int c1 = 1; c1 <= N; ++c1) {
                    for (int c2 = c1; c2 <= N; ++c2) {
                        long long sum = 0;
                        for(int x=c1;x<=c2;++x){
                            for(int y=r1;y<=r2;++y){
                                sum += grid[x][y];
                            }
                        }
                        if (sum > bestVal) {
                            bestVal = sum;
                            bestTLc = c1; bestTLr = r1; bestBRc = c2; bestBRr = r2;
                        }
                    }
                }
            }
        }

        if (bestVal <= 0) break;

        totalScore += bestVal;
        cout << "(" << bestTLc << ", " << bestTLr << ") (" << bestBRc << ", " << bestBRr << ") " << bestVal << "\n";

        for (int c = bestTLc; c <= bestBRc; ++c) {
            for (int r = bestTLr; r <= bestBRr; ++r) {
                grid[c][r] = 0;
            }
        }
        gravityDrop();
    }
    cout << totalScore << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    playGame();
    return 0;
}

---

2023 년 국선전 문제집 해설

문제 1: 문자열 암호 변환 (난이도 하)

특정 규칙에 따라 문자열을 변환하는 과정입니다. 대문자는 +1, 소문자는 -1 이동하며, 연달아 오는 알파벳이 3 개 이상일 경우 반대 성의로 변환됩니다.

구현 팁: 문자 하나하나의 타입을 판별하여 조건부 로직을 적용하고, 변환된 후 연속성 검사를 위해 별도의 플래그를 사용하는 것이 안전하다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string transformString(string str) {
    string temp = "";
    for (char c : str) {
        if (c >= 'A' && c <= 'Z') temp += ((c - 'A' + 1) % 26) + 'A';
        else if (c >= 'a' && c <= 'z') temp += ((c - 'a' - 1 + 26) % 26) + 'a';
        else temp += c;
    }
    return temp;
}

void handleLogic() {
    int n; 
    string s;
    if (!(cin >> n >> s)) return;
    if (s == "yourname") s = "accuber";
    
    cout << s << "\n";
    while(n--) {
        string curr = transformString(s);
        string nextS = "";
        int idx = 0;
        while(idx < curr.length()) {
            char type = (curr[idx] >= 'A' && curr[idx] <= 'Z') ? 'U' : 
                        (curr[idx] >= 'a' && curr[idx] <= 'z') ? 'L' : 'O';
            
            int cnt = 0;
            while(idx < curr.length()) {
                char t = (curr[idx] >= 'A' && curr[idx] <= 'Z') ? 'U' : 
                         (curr[idx] >= 'a' && curr[idx] <= 'z') ? 'L' : 'O';
                if (t != type) break;
                nextS += curr[idx];
                idx++;
                cnt++;
            }
            
            // 3 개 이상 연속이면 역변환
            if (type != 'O' && cnt >= 3) {
                for (int k = 0; k < cnt; ++k) {
                    char c = nextS[nextS.length() - 1 - k];
                    if ('U' == type) nextS[nextS.length() - 1 - k] = c - 'A' + 'a';
                    else nextS[nextS.length() - 1 - k] = c - 'a' + 'A';
                }
            }
        }
        s = nextS;
    }
    cout << s << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    handleLogic();
    return 0;
}

문제 2: 카드 게임 추측 (난이도 하중)

여러 플레이어가 특정 색상의 카드를 가지고 있을 때, 세 가지 색상 조합과 합 범위를 설정하여 정보를 제한하는 최적의 질문을 찾는 문제다.

구현 팁: 사용된 카드를 배제한 상태에서 가능한 모든 3 가지 색상 조합과 합 범력을 순회하며, 질문이 주는 정보량 (최대 불확실성 감축) 을 계산한다.

문제 3: 라면 주문 스케줄링 (난이도 중상)

가용 바구니와 조리를 진행 중인 바구니를 우선순위 큐로 관리하여 최소 시간에 주문을 완료하는 문제입니다. 시간 관리와 이벤트 기반 처리가 중요합니다.

핵심은 std::priority_queue 를 두 개 사용하여 available 와 cooking 상태를 분리 관리하는 것입니다.

문제 4: 블록 타워 해체 (난이도 상)

블록을 위로 쌓아올린 형태로 주어졌으며, 상위 블록이 제거되어야 하위 블록을 뺄 수 있습니다. 이는 전형적인 위상 정렬 문제입니다.

실무 코드: 진입 차수 (In-Degree) 를 계산하고, 0 인 노드를 힙에 담아 최小编号的인 블록을 먼저 출력합니다.

문제 5: 스택 병합 (난이도 상)

두 개의 스택에서 요소를 꺼내어 배열을 만들고, K 개의 동일한 숫자가 모이면 사라지는 규칙이 있습니다. 이를 만족하면서 중간 배열의 크기를 최소화하는 문제가 아니라, 최대 크기를 제한조건으로 두고 해결 여부를 판단하는 이분 탐색 문제입니다.

---

2022 년 국선전 문제집 해설

문제 1: 교통 신호 제어 (난이도 하)

버튼 클릭 타이밍을 기반으로 신호등의 빨간불 시간을 시뮬레이션하는 문제입니다. 단순히 이벤트를 시간 순서대로 처리하여 구간을 관리하면 됩니다.

문제 2: 여왕의 명령 (난이도 하중)

격자판 위에서 보드의 움직임 제약 사항 (공격 범위 회피) 을 만족하는 경로를 찾는 문제입니다. 격자가 작으므로 완전 탐색으로 가능한 시작점과 중간 정지점을 순회하고 조건을 검증합니다.

문제 3: 전리품 배분 (난이도 중상)

BFS 를 통해 층별 구조를 만든 뒤, 각 층마다 DP 를 수행하여 특정 플레이어에게 돌아갈 최대 가치를 구합니다. 최단 경로 상에서의 노드 선택 전략이 핵심입니다.

문제 4: 소 변화 편집 거리 (난이도 상)

두 수열 사이의 최소 수정 횟수 (편집 거리) 를 구하고 이를 재구성하는 문제입니다. 표준적인 DP 를 사용하며, 선택한 조작 (삽입, 삭제, 치환) 을 기록하여 결과를 복원합니다.

// 편집 거리 DP 로직 예시
// dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (match))
// path[i][j] 를 통해 어떻게 도달했는지 추적

문제 5: 커뮤니티 삼중집 합계산 (난이도 상)

트리 구조상 세 노드가 서로 등거리에 있고 종류가 다를 때의 경우의 수를 세는 문제입니다. 노드 수가 적을 때는 BFS 로 전수 계산을 수행하거나 중심점을 기준으로 삼방 조사 방식을 활용할 수 있습니다.