A - 값의 범위

주어진 값 r이 어느 범위에 속하는지 확인하고, 그 범위의 상한에서 r을 뺀 값을 출력하면 된다.

100 미만이면 100-r, 200 미만이면 200-r, 300 미만이면 300-r을 출력한다.

코드 확인하기

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

int main() {
    int r;
    cin >> r;
    
    if(r < 100) {
        cout << 100 - r;
    } else if(r < 200) {
        cout << 200 - r;
    } else if(r < 300) {
        cout << 300 - r;
    }
    
    return 0;
}

B - 작업 선택

n개의 작업 각각에 소요되는 시간 l[i]가 주어진다. 그 중 가장 오래 걸리는 p개의 작업을 선택할 때, 가장 빨리 끝나는 작업이 완료되는 때까지 남은 시간을 구한다.

전체 작업을 오름차순으로 정렬한 후, p번째로 큰 작업(정렬된 배열에서 n-p+1 위치)의 소요 시간을 구한다. 현재까지 경과한 시간 t에서 이를 빼면 남은 시간이 된다. 음수이면 0을 출력한다.

코드 확인하기

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

int main() {
    int n, t, p;
    cin >> n >> t >> p;
    
    vector<int> workTime(n+1);
    for(int i = 1; i <= n; ++i) {
        cin >> workTime[i];
    }
    
    sort(workTime.begin() + 1, workTime.begin() + n + 1);
    
    int requiredTime = workTime[n - p + 1];
    int answer = max(0, t - requiredTime);
    cout << answer;
    
    return 0;
}

C - 부분 문자열 회문

길이 n의 문자열이 주어진다. 각 알파벳의 사용 가능 횟수가 정해져 있을 때, 길이 k인 연속 부분 문자열 중 회문이 존재하지 않도록 문자열을 구성할 수 있는 경우의 수를 구한다.

알파벳별 사용 가능 횟수를 저장하고, 재귀적으로 문자열을 구성한다. 길이가 n이 되면, 길이 k인 모든 부분 문자열을 검사하여 회문이 없는 경우만 정답을 증가시킨다.

코드 확인하기

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

int n, k;
char inputStr[15];
char result[15];
int available[35];
int answer = 0;

void generate(int pos) {
    if(pos > n) {
        for(int i = 1; i + k - 1 <= n; ++i) {
            bool isPalindrome = true;
            for(int j = 0; j < k/2; ++j) {
                if(result[i + j] != result[i + k - 1 - j]) {
                    isPalindrome = false;
                    break;
                }
            }
            if(isPalindrome) return;
        }
        answer++;
        return;
    }
    
    for(char c = 'a'; c <= 'z'; ++c) {
        int idx = c - 'a';
        if(available[idx] == 0) continue;
        
        result[pos] = c;
        available[idx]--;
        generate(pos + 1);
        available[idx]++;
    }
}

int main() {
    cin >> n >> k >> (inputStr + 1);
    
    for(int i = 1; i <= n; ++i) {
        available[inputStr[i] - 'a']++;
    }
    
    generate(1);
    cout << answer;
    
    return 0;
}

D - 회문 수의 순서

d자리의 회문 수 중에서 k번째 큰수를 찾는 문제다. 회문 수는 앞부분이 결정되면 뒤부분이 자동으로 정해진다. 첫 번째 자리는 0이 될 수 없으므로 항상 1부터 시작한다.

d자리 회문 수의 개수는 9 × 10^⌊(d+1)/2⌋-1 개이다. k에서 각 자리의 개수를 빼면서 해당 자릿수를 찾고, 찾으면 해당 회문수를 문자열로 구성하여 출력한다.

코드 확인하기

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

long long power10(int exp) {
    long long result = 1;
    for(int i = 0; i < exp; ++i) {
        result *= 10;
    }
    return result;
}

int main() {
    long long k;
    cin >> k;
    
    if(k == 1) {
        cout << 0;
        return 0;
    }
    k--;
    
    for(int digits = 1; ; ++digits) {
        int halfDigits = (digits + 1) / 2;
        long long count = 9 * power10(halfDigits - 1);
        
        if(k < count) {
            long long baseNum = power10(halfDigits - 1) + k;
            string s = to_string(baseNum);
            
            while(s.length() < digits) {
                s.push_back(' ');
            }
            
            for(int i = halfDigits; i < digits; ++i) {
                s[i] = s[digits - 1 - i];
            }
            
            cout << s;
            return 0;
        } else {
            k -= count;
        }
    }
    
    return 0;
}