T1 - 차분 누적 계산

정수 배열에서 모든 쌍에 대해 후항과 전항의 차를 구한 후, 이 차들의 합을 다시 계산한다. 예를 들어 수열 a₁, a₂, a₃, a₄에 대해 다음과 같은 결과를 도출해야 한다:

(a₂−a₁) − (a₃−a₁) − (a₃−a₂) − (a₄−a₁) − (a₄−a₂) − (a₄−a₃)

입력: 첫째 줄에 정수 n, 둘째 줄에 n개의 정수 a₁~aₙ

출력: 최종 결과값 (정수)

제약 조건: - 50% 데이터: 1 ≤ n ≤ 500, 1 ≤ aᵢ ≤ 500 - 50% 데이터: 1 ≤ n ≤ 500,000, 1 ≤ aᵢ ≤ 500,000

예제 입력:

3
1 2 3

예제 출력:

-2

해법: 직접 반복문으로 모든 쌍을 처리하면 시간 복잡도가 O(n²)로 제한에 걸리며, 50점만 획득 가능하다. 이를 개선하기 위해 공식을 전개하여 각 원소의 등장 횟수를 분석한다.

전개 결과, 각 원소 aᵢ는 양의 기여와 음의 기여로 나뉘며, 전체적으로 다음과 같은 패턴이 나타난다:

• a₁은 음수로 -(n-1)번 등장
• a₂부터 aₙ₋₁까지는 +i번, -(n-i)번 등장
• aₙ은 음수로 -(n-1)번 등장

이를 이용해 선형 시간 알고리즘으로 해결할 수 있다.

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

long long n, a[500010], prefix[500010];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i-1] + a[i];
    }

    long long result = a[2] - a[1];
    for (int i = 2; i < n; ++i) {
        result += prefix[i];  // 이전 항목의 누적합 추가
    }
    for (int i = 3; i <= n; ++i) {
        result -= a[i] * (i - 1);  // 각 항목이 몇 번 감산되는지 계산
    }

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

T2 - 이진수 비트 연산

두 이진 문자열을 입력받아, 각 비트별로 XOR 연산을 수행하고 결과를 이진수 형태로 출력한다. 동일하면 0, 다르면 1.

입력: 두 줄에 걸쳐 이진 문자열 (길이 최대 100)

출력: XOR 결과 이진수 (앞서 있는 0 제거)

예제:

입력:
1101
1110

출력:
11

해법: 길이가 다를 수 있으므로 짧은 수에 앞부분에 0을 추가하여 길이 맞춤. 이후 뒤에서부터 비트 비교 후 결과 문자열 생성. 마지막으로 앞부분의 0을 제거한다.

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

string s1, s2, res;

int main() {
    cin >> s1 >> s2;
    
    int len1 = s1.length(), len2 = s2.length();
    while (len1 < len2) s1 = '0' + s1, len1++;
    while (len2 < len1) s2 = '0' + s2, len2++;

    for (int i = 0; i < len1; ++i) {
        if (s1[i] == s2[i]) res += '0';
        else res += '1';
    }

    // 앞부분 0 제거
    int start = 0;
    while (start < res.length() && res[start] == '0') start++;
    
    if (start == res.length()) cout << "0";
    else for (int i = start; i < res.length(); ++i) cout << res[i];
    cout << endl;

    return 0;
}

T3 - 이모티콘 분석

채팅 메시지에서 :-)는 긍정 감정, :-(는 부정 감정을 의미한다. 전체 메시지에서 긍정 감정 수와 부정 감정 수의 차를 반환한다.

입력: 한 줄의 문자열 (단어들로 구성됨)

출력: 긍정 - 부정 값

예제:

입력:
Hello :-), how are you? :-(
출력:
0

해법: 단어 단위로 입력을 읽으며, :-)와 :-(를 찾아 카운트한다.

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

int happy = 0, sad = 0;
string word;

int main() {
    while (cin >> word) {
        if (word == ":-)") happy++;
        else if (word == ":-(") sad++;
    }
    cout << happy - sad << endl;
    return 0;
}

T4 - 동일 요소 연속 부분 배열 세기

배열에서 모든 요소가 동일한 연속 부분 배열의 개수를 세는 문제. 예: [1,1,2,2,2] → [1],[1],[1,1],[2],[2],[2],[2,2],[2,2,2] 등.

해법: 연속된 동일 요소 그룹을 분류한 후, 각 그룹의 길이 m에 대해 m*(m+1)/2 만큼의 부분 배열이 존재한다.

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

const int MAXN = 1e5 + 10;
long long n, arr[MAXN], groupCount[MAXN], groupSize = 1;

int main() {
    cin >> n;
    cin >> arr[1];
    for (int i = 2; i <= n; ++i) {
        cin >> arr[i];
        if (arr[i] == arr[i-1]) {
            groupCount[groupSize]++;
        } else {
            groupSize++;
            groupCount[groupSize]++;
        }
    }

    long long total = 0;
    for (int i = 1; i <= groupSize; ++i) {
        total += (groupCount[i] + 1) * groupCount[i] / 2;
    }

    cout << total << endl;
    return 0;
}

T5 - 관광 자전거 대여 최소화

각 자전거는 최대 2명까지 탑승 가능하며, 두 사람의 체중 합은 제한치 T를 초과하면 안 된다. n명의 학생 중 최소 몇 대의 자전거를 빌려야 하는지 계산한다.

입력: 첫째 줄에 n, T, 둘째 줄에 각 학생의 체중

출력: 최소 대수

예제:

입력:
7 50
15 41 32 42 27 25 19
출력:
5

해법: 그리디 알고리즘 적용. 가장 낮은 체중과 가장 높은 체중을 비교하여 합이 T 이하라면 함께 태우고, 그렇지 않으면 무거운 쪽은 혼자 타게 한다.

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

long long n, T, weights[100010], ans = 0;

int main() {
    cin >> n >> T;
    for (int i = 1; i <= n; ++i) cin >> weights[i];
    sort(weights + 1, weights + n + 1);

    int left = 1, right = n;
    while (left <= right) {
        if (weights[left] + weights[right] <= T) {
            left++;  // 작은 건 큰 거랑 짝짓기
        }
        right--;     // 큰 건 항상 하나씩 빼기
        ans++;
    }

    cout << ans << endl;
    return 0;
}