문제 링크:

https://codeforces.com/contest/1118

A 문제:

문제 설명:

q 번의 쿼리가 주어지며, 각 쿼리마다 숫자 n 이 주어집니다. 숫자 1 과 2 를 사용하여 n 을 만들되, 1 의 비용은 a이고 2 의 비용은 b입니다. 최소 비용을 구하세요.

해결 방법:

만약 2a <= b라면 모두 1로 구성하는 것이 가장 유리합니다. 반면에 2a > b라면, n이 홀수라면 하나의 1과 나머지를 2로, 짝수라면 모두 2로 구성하면 됩니다.

코드 예시:

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

int main(){
    int q;
    cin >> q;
    while(q--){
        long long n, a, b;
        cin >> n >> a >> b;
        if(2 * a <= b){
            cout << n * a << "\n";
        }
        else{
            cout << (n / 2) * b + ((n % 2) * a) << "\n";
        }
    }
}

View Code

B 문제:

문제 설명:

n 개의 수가 주어졌을 때, 그 중 하나를 제거한 후 남은 수들의 순서를 유지한 상태에서 홀수 인덱스와 짝수 인덱스의 합이 동일해지는 경우의 수를 계산하세요.

해결 방법:

특정 수를 제거하면 그 이후의 수들은 인덱스의 홀짝성이 바뀌게 됩니다. 이를 고려하여 홀수와 짝수 인덱스의 누적합을 계산하여 비교하면 됩니다.

코드 예시:

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

const int MAXN = 200005;
long long arr[MAXN], oddSum[MAXN], evenSum[MAXN];

int main(){
    int n;
    cin >> n;
    for(int i=1; i<=n; ++i){
        cin >> arr[i];
        oddSum[i] = oddSum[i-1];
        evenSum[i] = evenSum[i-1];
        if(i%2 == 1) oddSum[i] += arr[i];
        else evenSum[i] += arr[i];
    }
    int result = 0;
    for(int i=1; i<=n; ++i){
        if(oddSum[i-1] + (evenSum[n] - evenSum[i]) == evenSum[i-1] + (oddSum[n] - oddSum[i])){
            result++;
        }
    }
    cout << result;
}

View Code

C 문제:

문제 설명:

nxn 크기의 행렬을 구성하되, 모든 행과 열이 팬더롬(palindrome)이 되도록 하세요.

해결 방법:

주어진 조건에 따라 행렬을 구성하면 됩니다.

코드 예시:

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

const int MAXN = 25;
int matrix[MAXN][MAXN], countArr[1007];

int main(){
    int n;
    cin >> n;
    for(int i=0; i<n*n; ++i){
        int x;
        cin >> x;
        countArr[x]++;
    }
    if(n % 2 == 0){
        for(int i=1; i<=1000; ++i){
            if(countArr[i] % 4 != 0){
                cout << "NO\n";
                return 0;
            }
        }
        // Construct matrix here...
    }
    else{
        // Similar logic as above...
    }
    cout << "YES\n";
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            cout << matrix[i][j] << " ";
        }
        cout << "\n";
    }
}

View Code

D 문제:

문제 설명:

커피와 과제가 주어졌을 때, 최소한의 날짜 안에 과제를 완료해야 합니다.

해결 방법:

커피의 효과를 내림차순으로 정렬한 후, 이분 탐색을 통해 필요한 최소 날짜를 찾습니다.

코드 예시:

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

bool isValid(vector<int>& coffee, int days, int pages){
    long long total = 0;
    int penalty = 0;
    for(int i=0; i<days && i<coffee.size(); ++i){
        total += coffee[i];
    }
    for(int i=days; i<coffee.size(); ++i){
        penalty++;
        if(coffee[i] - penalty > 0){
            total += coffee[i] - penalty;
        }
        else break;
    }
    return total >= pages;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> coffee(n);
    long long sum = 0;
    for(auto &x : coffee){
        cin >> x;
        sum += x;
    }
    if(sum < m){
        cout << "-1\n";
        return 0;
    }
    sort(coffee.rbegin(), coffee.rend());
    int left = 1, right = n, answer = n;
    while(left <= right){
        int mid = (left + right)/2;
        if(isValid(coffee, mid, m)){
            answer = mid;
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }
    cout << answer;
}

View Code