문제 1: 외톨이 사진(Lonely Photo)

농장주 존이 N마리의 소를 새로 샀다. 각 소는 게른지(Guernsey) 또는 홀스틴(Holstein) 품종이다. 소들이 한 줄로 서 있을 때, 길이가 3 이상인 모든 연속 구간에 대해 사진을 찍는다. 단, 구간 내에 특정 품종이 정확히 한 마리만 존재하는 "외톨이 사진"은 폐기처분한다. 폐기되는 사진의 총 개수를 구하라.

입력

• 첫 줄: N (소의 수)
• 둘째 줄: 길이 N의 문자열 (G: 게른지, H: 홀스틴)

출력

외톨이 사진의 개수

접근법 1: 완전 탐색 O(N³)

모든 구간을 직접 확인하는 방법. 각 구간에서 G와 H의 개수를 세어 하나가 1이면 카운트.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    freopen("lonelyphoto.in", "r", stdin);
    freopen("lonelyphoto.out", "w", stdout);
    
    long long n, result = 0;
    string cows;
    cin >> n >> cows;
    
    for (long long start = 0; start < n; ++start) {
        for (long long end = start + 2; end < n; ++end) {
            long long cntG = 0, cntH = 0;
            for (long long idx = start; idx <= end; ++idx) {
                if (cows[idx] == 'G') cntG++;
                else cntH++;
            }
            if (cntG == 1 || cntH == 1) result++;
        }
    }
    
    cout << result << "\n";
    return 0;
}

접근법 2: 누적합 최적화 O(N²)

구간 합을 빠르게 구하기 위해 누적합 배열 활용.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    freopen("lonelyphoto.in", "r", stdin);
    freopen("lonelyphoto.out", "w", stdout);
    
    long long n, answer = 0;
    string herd;
    cin >> n >> herd;
    
    vector<long long> prefixG(n + 1, 0), prefixH(n + 1, 0);
    
    for (long long i = 0; i < n; ++i) {
        prefixG[i + 1] = prefixG[i] + (herd[i] == 'G');
        prefixH[i + 1] = prefixH[i] + (herd[i] == 'H');
    }
    
    for (long long left = 0; left < n - 2; ++left) {
        for (long long right = left + 2; right < n; ++right) {
            long long gCount = prefixG[right + 1] - prefixG[left];
            long long hCount = prefixH[right + 1] - prefixH[left];
            if (gCount == 1 || hCount == 1) answer++;
        }
    }
    
    cout << answer << "\n";
    return 0;
}

접근법 3: 선형 시간 O(N)

핵심 관찰: 길이 3 이상인 구간에서 "외톨이"가 되려면, 한 품종이 1마리이고 다른 품종이 2마리 이상이어야 한다. 각 위치를 중심으로 최대 확장 범위를 계산.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    freopen("lonelyphoto.in", "r", stdin);
    freopen("lonelyphoto.out", "w", stdout);
    
    int n;
    long long total = 0;
    string seq;
    cin >> n >> seq;
    
    vector<int> nextG(n + 2, n), nextH(n + 2, n);
    vector<int> secondG(n + 2, n), secondH(n + 2, n);
    
    for (int i = n - 1; i >= 0; --i) {
        nextG[i] = (seq[i] == 'G') ? i : nextG[i + 1];
        nextH[i] = (seq[i] == 'H') ? i : nextH[i + 1];
    }
    
    for (int i = n - 1; i >= 0; --i) {
        secondG[i] = (nextG[i] + 1 < n) ? nextG[nextG[i] + 1] : n;
        secondH[i] = (nextH[i] + 1 < n) ? nextH[nextH[i] + 1] : n;
    }
    
    for (int pos = 0; pos < n; ++pos) {
        int farG = secondG[pos];
        int farH = secondH[pos];
        
        int limitG = max(nextG[pos], pos + 2);
        int limitH = max(nextH[pos], pos + 2);
        
        total += max(0, farG - limitG);
        total += max(0, farH - limitH);
    }
    
    cout << total << "\n";
    return 0;
}

문제 2: 허들(Herdle)

3×3 그리드에서 정답과 추측을 비교하여 초록색(위치와 문자 일치)과 노색(문자는 일치하나 위치 불일치) 타일 개수를 출력.

규칙

• 초록색: 같은 위치에 같은 문자
• 노란색: 문자는 존재하나 위치가 다름. 단, 정답에 남은 개수만큼만 카운트

해결 전략

1. 초록색 먼저 체크
2. 초록색이 아닌 위치에서 각 문자의 출현 빈도 계산
3. 정답과 추측의 빈도 중 작은 값을 노란색으로 합산

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    freopen("herdle.in", "r", stdin);
    freopen("herdle.out", "w", stdout);
    
    vector<string> secret(3), guess(3);
    for (int i = 0; i < 3; ++i) cin >> secret[i];
    for (int i = 0; i < 3; ++i) cin >> guess[i];
    
    int green = 0, yellow = 0;
    vector<int> secretFreq(26, 0), guessFreq(26, 0);
    
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            if (secret[r][c] == guess[r][c]) {
                green++;
            } else {
                secretFreq[secret[r][c] - 'A']++;
                guessFreq[guess[r][c] - 'A']++;
            }
        }
    }
    
    for (int ch = 0; ch < 26; ++ch) {
        yellow += min(secretFreq[ch], guessFreq[ch]);
    }
    
    cout << green << "\n" << yellow << "\n";
    return 0;
}