주간 개요

이번 주는 생활 리듬이 불규칙하여 학습 효율이 저하되었고, 이를 개선하기 위해 환경을 변경하였다. 새로운 일정으로 인해 다음 주부터는 더 체계적인 학습과 경기 준비를 할 계획이다.

문제 해결 기록

SMU Winter 2025 Round 6

B. 스트리머의 밤

문제 요약: 여러 프로그램의 시작 및 종료 시간이 주어질 때, 전체 시간 내에 볼 수 있는 최대 프로그램 수를 구하는 문제.

접근 방식: 각 프로그램의 종료 시간을 기준으로 정렬한 후, 끝나는 시점이 가장 빠른 것부터 차례로 선택하는 그리디 전략을 사용한다.

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

struct Program {
    ll start, end;
};

bool compare(const Program& a, const Program& b) {
    return a.end < b.end;
}

void solve() {
    ll n, total_time;
    cin >> n >> total_time;
    
    vector<Program> programs(n);
    for (ll i = 0; i < n; ++i) {
        cin >> programs[i].start >> programs[i].end;
    }

    sort(programs.begin(), programs.end(), compare);

    ll count = 1;
    ll last_end = programs[0].end;

    for (ll i = 1; i < n; ++i) {
        if (programs[i].start >= last_end) {
            last_end = programs[i].end;
            count++;
        }
    }

    cout << count << endl;
}

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

    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

피드백: 처음에는 현재 프로그램의 시작 시간과 이전 선택된 프로그램의 종료 시간만 비교했지만, 이는 잘못된 선택을 유도할 수 있다. 정렬 기준은 종료 시간만 고려하면 되며, 종료가 빠른 순서로 선택하면 항상 최적해를 얻을 수 있다.

E. 축구 토너먼트

문제 요약: 각 팀은 실력 값이 있으며, 두 팀 간 경기에서 승리 시 3점, 무승부 시 2점, 패배 시 0점을 받는다. 한 번의 훈련으로 어떤 팀의 실력을 1만큼 증가시킬 수 있을 때, 모든 팀의 총 점수를 최대로 만들기 위한 최소 훈련 횟수를 구한다.

접근 방식: 모든 팀의 실력이 단조 증가하는 상태(즉, 비감소 순서)가 되면 총 점수가 최대화된다. 따라서 배열을 오름차순 정렬하고, 앞 원소보다 작거나 같은 경우 그 차이만큼 추가적으로 늘려주면 된다.

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

void solve() {
    ll n;
    cin >> n;
    vector<ll> skills(n);
    for (ll i = 0; i < n; ++i) {
        cin >> skills[i];
    }

    sort(skills.begin(), skills.end());

    ll extra_train = 0;
    for (ll i = 1; i < n; ++i) {
        if (skills[i] <= skills[i-1]) {
            extra_train += skills[i-1] - skills[i] + 1;
            skills[i] = skills[i-1] + 1;
        }
    }

    cout << extra_train << endl;
}

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

    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

피드백: 초기 접근은 매번 실력을 1씩 늘린 후 다시 정렬하는 방식이었으나, 이는 시간 초과로 이어졌다. 하지만 예시를 분석하면서 단조 증가 상태가 최적임을 확인하고, 이후에는 바로 직전 원소보다 1 크게 설정하는 방식으로 해결했다.

F. 천문학

문제 요약: 매우 큰 정수 두 개를 더하는 문제. 일반적인 자료형으로 처리 불가능.

접근 방식: 문자열로 입력받아 길이를 맞추고, 뒤에서부터 하나씩 더하며 자릿수 올림을 처리한다. 결과는 역순으로 저장 후 마지막에 반전하여 출력한다.

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

void solve() {
    string num1, num2;
    cin >> num1 >> num2;

    int len1 = num1.length(), len2 = num2.length();
    int max_len = max(len1, len2);

    // 앞쪽에 0 채우기
    while (num1.length() < max_len) num1 = '0' + num1;
    while (num2.length() < max_len) num2 = '0' + num2;

    string result;
    int carry = 0;

    for (int i = max_len - 1; i >= 0; --i) {
        int digit1 = num1[i] - '0';
        int digit2 = num2[i] - '0';
        int sum = digit1 + digit2 + carry;
        carry = sum / 10;
        result.push_back((sum % 10) + '0');
    }

    if (carry) {
        result.push_back('1');
    }

    reverse(result.begin(), result.end());
    cout << result << endl;
}

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

    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

피드백: 경기 중 제출한 코드와 동일하지만, 논리적 접근이 명확하고 유지보수가 쉬워서 기록해두었다.

SMU Winter 2025 Round 8

C. 음수와 양수

문제 요약: 배열의 인접한 두 원소를 동시에 부호 바꾸는 연산을 무제한으로 수행할 수 있을 때, 배열의 합을 최대화하는 방법을 찾는 문제.

접근 방식: 음수의 개수가 짝수면 모두 양수로 만들 수 있고, 홀수면 절댓값이 가장 작은 원소만 음수로 남겨야 한다. 따라서 절댓값의 합에서 해당 값을 두 배 빼면 된다.

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

void solve() {
    ll n;
    cin >> n;
    vector<ll> arr(n);
    ll neg_count = 0;
    ll total_abs = 0;
    ll min_abs = LLONG_MAX;

    for (ll i = 0; i < n; ++i) {
        cin >> arr[i];
        total_abs += abs(arr[i]);
        if (arr[i] < 0) neg_count++;
        min_abs = min(min_abs, abs(arr[i]));
    }

    if (neg_count % 2 == 0) {
        cout << total_abs << '\n';
    } else {
        cout << total_abs - 2 * min_abs << '\n';
    }
}

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

    ll t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

피드백: 초기에는 인접 쌍의 9가지 경우를 모두 나누어 생각하며 복잡하게 접근했지만, 사실은 부호 변환의 성질을 활용하면 단순한 규칙으로 해결 가능하다. 특히, 인접 원소의 부호를 자유롭게 조작할 수 있다는 점이 핵심이다.

H. 사탕을 가져가라

문제 요약: n개의 사탕 봉투가 있으며, 한 아이는 짝수 개의 사탕을 가진 봉투를, 다른 아이는 홀수 개의 봉투를 가져간다. 사탕을 적절히 정렬하여, 어떤 시점에서도 첫 번째 아이의 총 사탕 수가 두 번째 아이보다 항상 크도록 할 수 있는지를 묻는 문제.

접근 방식: 짝수 봉투의 총합이 홀수 봉투의 총합보다 클 경우, 먼저 짝수 봉투를 모두 가져가는 것으로 항상 우위를 유지할 수 있다.

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

void solve() {
    ll n;
    cin >> n;
    ll even_sum = 0, odd_sum = 0;

    for (ll i = 0; i < n; ++i) {
        ll candy;
        cin >> candy;
        if (candy % 2 == 0) {
            even_sum += candy;
        } else {
            odd_sum += candy;
        }
    }

    if (even_sum > odd_sum) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

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

    ll t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

피드백: 경기 후반부에 피로감이 누적되어 문제 해결에 실패했다. 생활 리듬 개선이 필수적이라는 것을 다시 한번 느꼈다.

주간 회고

첫 주 대비 다소 발전했으며, STL 사용 능력이 향상되었고, 경기 중 집중력도 유지할 수 있게 되었다. 이번 주에는 기존 미완의 문제들을 완성하고, 다양한 대회에 참여해 경험을 쌓는 것을 목표로 한다. 새 환경에서의 도전을 위해, 우선 동적계획법과 탐색 알고리즘(DFS/BFS), C++ 언어 특성 등을 복습할 계획이며, 3월 말 예정인 컴퓨터 시험 준비에도 박차를 가할 것이다.