절댓값 부등식을 이용한 최소 거리 선택

절댓값의 성질에 따르면 |x-a| + |x+b| ≥ |a-b| 이며 등호가 성립하려면 x는 a와 b 사이에 위치해야 합니다. 따라서 각 점에서 특정 x까지의 거리 합을 최소화하려면 x는 중앙값에 위치해야 합니다.

주어진 숫자 집합으로 만들 수 없는 최소 양수 찾기

[1,x] 범위의 모든 수를 만들 수 있을 때, 사용하지 않은 가장 작은 수가 a라면 두 가지 경우가 있습니다:

• a > x + 1이라면 x+1은 만들 수 없습니다
• a ≤ x + 1이라면 [1,x+a] 범위까지 확장할 수 있습니다

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
using ll = long long;
const int MAX_N = 1e5 + 100;

int count_n;
int values[MAX_N];

int main(){
    scanf("%d",&count_n);
    
    for(int idx = 1; idx <= count_n; idx++) 
        scanf("%d",&values[idx]);
    
    sort(values + 1, values + count_n + 1);
    ll current_sum = 0;
    
    for(int idx = 1; idx <= count_n; idx++){
        if(values[idx] <= current_sum + 1) 
            current_sum += values[idx];
        else 
            break;
    }
   
    printf("%lld\n",current_sum + 1);
    return 0;
}

최대한 멀리 이동 후 연료 보충하기

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

#define ll long long
#define endl "\n"
const int max_stations = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

pair<int, int> stations[max_stations];

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

    int destination, station_count, fuel;
    cin >> destination >> station_count >> fuel;
    priority_queue<int> fuel_heap;

    for (int i = 0; i < station_count; i++)
        cin >> stations[i].first >> stations[i].second;
    
    sort(stations, stations + station_count);
    int refuel_count = 0;

    for (int i = 0; i < station_count; i++){
        if (stations[i].first > fuel){
            if (!fuel_heap.empty() && fuel_heap.top() >= stations[i].first){
                fuel = fuel_heap.top();
                refuel_count++;
            } else {
                cout << "-1" << endl;
                return 0;
            }
        }
       fuel_heap.push(stations[i].first + stations[i].second);
    }
    
    if (fuel < destination)
        fuel = fuel_heap.top(), refuel_count++;

    if (fuel >= destination)
        cout << refuel_count << endl;
    else
        cout << "-1" << endl;
        
    return 0;
}

가위바위보 게임 결과 분석

번호 순서를 모르는 상태에서 최대 승리 횟수를 구하는 문제입니다. 가위(1), 바위(2), 보(3)의 관계에서 인접한 번호쌍 (1,2), (2,3), (3,1)은 승패 관계를 가집니다. 번호를 0부터 시작하도록 조정하면 (x+1)%3로 다음 손勢을 표현할 수 있습니다.

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

int main() {
    int rounds;
    cin >> rounds;
    int win_a = 0, win_b = 0;
    
    for(int i = 0; i < rounds; ++i) {
        int player1, player2;
        cin >> player1 >> player2;
        player1--; player2--;
        
        if((player1 + 1) % 3 == player2) win_a++;
        if(player1 == (player2 + 1) % 3) win_b++;
    } 
    
    cout << max(win_a, win_b) << endl;
    return 0;
}

수위 상승 시 섬의 개수 변화

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

#define x first
#define y second
const int LIMIT = 1e5+10;
typedef pair<int, int> Point;

int heights[LIMIT];
Point sorted_points[LIMIT];

int main() {
    int length;
    cin >> length;
    
    for (int i = 1; i <= length; i++) 
        cin >> heights[i];
        
    length = unique(heights+1, heights+length+1) - heights - 1;
    heights[length+1] = 0;
    
    for (int i = 1; i <= length; i++) {
        sorted_points[i] = {heights[i], i};
    }
    
    sort(sorted_points+1, sorted_points+length+1);
    int max_islands = 1, current_count = 1;
    
    for (int i = 1; i <= length; i++) {
        int position = sorted_points[i].y;
        
        if(heights[position] > heights[position-1] && heights[position] > heights[position+1]) 
            current_count--;
        else if(heights[position] < heights[position-1] && heights[position] < heights[position+1]) 
            current_count++;
        
        if(sorted_points[i].x != sorted_points[i+1].x)
            max_islands = max(max_islands, current_count);
    }
    
    cout << max_islands;
    return 0;
}

뒤에서부터 역순 정렬 지점 찾기

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

const int SIZE = 110;
int sequence[SIZE];

int main() {
    int size;
    cin >> size;
    
    for (int i = 1; i <= size; i++) 
        cin >> sequence[i];
    
    for(int i = size - 1; i; i--) {
        if(sequence[i] > sequence[i+1]) {
            cout << i;
            return 0;
        }
    }
    
    cout << 0;
    return 0;
}

인접 원소 합 배열 복원

b[i] = a[i] + a[i+1] 관계를 이용하여 a[1] 값을 결정하면 전체 배열을 복원할 수 있습니다.

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

const int ARRAY_SIZE = 1e3+10;
int original[ARRAY_SIZE], sum_array[ARRAY_SIZE];
bool visited[ARRAY_SIZE];

bool validate(int first_value) {
    memset(visited, 0, sizeof(visited));
    memset(original, 0, sizeof(original));
    
    original[1] = first_value;
    visited[first_value] = true;
    
    for (int i = 2; i <= n; i++) {
        original[i] = sum_array[i-1] - original[i-1];
        
        if(original[i] < 1 || original[i] > n) 
            return false;
        if(visited[original[i]]) 
            return false;
            
        visited[original[i]] = true;
    }
    
    for (int i = 1; i <= n; i++)
        cout << original[i] << " ";
        
    return true;
}

int main() {
    cin >> n;
    for(int i = 1; i < n; i++) 
        cin >> sum_array[i];
    
    for (int i = 1; i <= n; i++)
        if(validate(i)) 
            break;
            
    return 0;
}

문자열 구간 수정 최소 횟수

두 문자열에서 다른 부분만을 연속 구간으로 묶어 수정 횟수를 계산합니다.

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

int length;
string str1, str2;

int main() {
    cin >> length >> str1 >> str2;
    int operations = 0, end_pos = -1;
    
    for (int start = 0; start < length; start++) {
        if(str1[start] != str2[start]) {
            end_pos = start + 1;
            while(end_pos < length && str1[end_pos] != str2[end_pos]) 
                end_pos++;
            operations++;
            start = end_pos;
        }
    }
    
    cout << operations;
    return 0;
}

감염 확산 최소 출발점 수

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

#define x first
#define y second
typedef pair<int,int> CowPosition;
const int MAX_COWS = 1010;

int cow_count;
CowPosition cows[MAX_COWS];

int main() {
    cin >> cow_count;
    
    for (int i = 1; i <= cow_count; i++) 
        cin >> cows[i].x >> cows[i].y;
        
    sort(cows+1, cows+cow_count+1);
    
    int min_radius = 1e8;
    for (int i = 1; i < cow_count; i++) {
        if(cows[i].y != cows[i+1].y) 
            min_radius = min(min_radius, cows[i+1].x - cows[i].x);
    }
    
    min_radius--;
    int groups = 0; int next_idx;
    
    for (int i = 1; i <= cow_count; i++) {
        if(cows[i].y) {
            next_idx = i + 1;
            while(next_idx <= cow_count && cows[next_idx].y && 
                  cows[next_idx].x - cows[next_idx-1].x <= min_radius) 
                next_idx++;
                
            groups++;
            i = next_idx - 1;
        }    
    }
    
    cout << groups;
    return 0;
}

개미 충돌 시뮬레이션

개미들이 서로 통과하는 것으로 생각하면, 특정 방향으로 이동하는 개미가 다른 방향의 개미들과 만나는 경우만 고려하면 됩니다.

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

const int ANT_LIMIT = 55;
int ant_count;
int positions[ANT_LIMIT];

int main() {
    cin >> ant_count;
    for (int i = 0; i < ant_count; i++) 
        cin >> positions[i];

    int left_moving = 0, right_moving = 0;
    
    for (int i = 1; i < ant_count; i++) {
        if (abs(positions[i]) < abs(positions[0]) && positions[i] > 0) 
            left_moving++;
        else if (abs(positions[i]) > abs(positions[0]) && positions[i] < 0) 
            right_moving++;
    }

    if ((positions[0] > 0 && right_moving == 0) || 
        (positions[0] < 0 && left_moving == 0)) 
        cout << 1 << endl;
    else 
        cout << left_moving + right_moving + 1 << endl;

    return 0;
}

문자열 순서 검사

const int ALPHABET = 27;
int order_position[ALPHABET];

int main() {
    string pattern, target;
    cin >> pattern;
    
    for (int i = 0; i < pattern.size(); i++)
        order_position[pattern[i]-'a'] = i;
        
    cin >> target;
    int segments = 1;
    
    for (int i = 1; i < target.size(); i++)
        if(order_position[target[i]-'a'] <= order_position[target[i-1]-'a'])
            segments++;
            
    cout << segments;
    return 0;
}

정수 연결 연산

임의의 두 숫자를 연결하여 ai+bi 형태로 만들 때, a[i] × 10^(⌊log10 a[j]⌋+1) % k 값이 특정 조건을 만족하는 경우를 세는 문제입니다.

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long LL;
const int LIMIT = 100010;
int power_mod_count[11][LIMIT];
int number_count;
LL numbers[LIMIT];
int divisor;
LL result;

int main() {
    cin >> number_count >> divisor;
    for(int i = 0; i < number_count; i++)
        cin >> numbers[i];

    for(int i = 0; i < number_count; i++) {
        LL remainder = numbers[i] % divisor;
        for(int j = 0; j < 11; j++) {
            power_mod_count[j][remainder]++;
            remainder = remainder * 10 % divisor;
        }            
    }

    for(int i = 0; i < number_count; i++) {
        LL current_mod = numbers[i] % divisor;
        int digits = to_string(numbers[i]).size();
        result += power_mod_count[digits][(divisor - current_mod) % divisor];

        LL validation = current_mod;
        while(digits--) 
            validation = validation * 10 % divisor;
            
        if(validation == (divisor - current_mod) % divisor) 
            result--;
    }

    cout << result << endl;
    return 0;
}

파스칼 삼각형 위치 찾기

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

typedef long long LL;
int target_value;

LL combination(int total, int select) {
    LL value = 1;
    for(int i = total, j = 1; j <= select; i--, j++) {
        value = value * i / j;
        if(value > target_value) 
            return value;
    }
    return value;
}

bool find_position(int diagonal) {
    int left = 2 * diagonal, right = max(target_value, left);
    while(left < right) {
        int mid = left + right >> 1;
        if(combination(mid, diagonal) >= target_value) 
            right = mid;
        else 
            left = mid + 1;
    }
    
    if(combination(right, diagonal) != target_value) 
        return false;
        
    cout << 1ll * (right + 1) * right / 2 + diagonal + 1 << endl;
    return true;
}

int main() {
    cin >> target_value;
    for(int diag = 16;; diag--)
        if(find_position(diag)) 
            break;
            
    return 0;
}