백준 34234 받아쓰기

https://www.acmicpc.net/problem/34234

 

샤라웃투jsj0412

케이스워크가 빡셌다.

 

$S_S[i] = S_K[i] = S_H[i]$인 인덱스 $i$는 순위에 아무 영향을 끼치지 않으므로 없다고 생각해도 된다. 나아가 $S_S$, $S_K$, $S_H$ 중 서로 완전히 같은 쌍이 있다면 둘의 순위가 다를 수 없으니 불가능하다. 이러한 케이스를 배제하고 생각하자. 

 

당연히 등수가 높은 문자열과 많이 매칭되도록 정답 문자열을 구성해야 할 것이다. 이를 조금 더 구체화해 보자. 우선 3등의 점수를 0으로 만들고 1등의 점수를 최대한 높이기 위해 정답 문자열의 $i$번 문자를 다음과 같이 설정하자.

 

• $S_S[i] = S_H[i]$라면 $S_S[i]$, $S_K[i]$, $S_H[i]$ 모두와 다른 문자를 사용한다.
• $S_S[i] \ne S_H[i]$라면 $S_S[i]$를 사용한다.

이렇게 정답 문자열을 만들면 1등 >= 2등 >= 3등 = 0이 된다. 이때 점수가 1등 > 2등 > 3등을 만족한다면 그대로 끝내면 되고, 1등의 점수가 1 이하라면 어떻게 해도 답을 구성할 수 없다. 남은 케이스는 1등 = 2등이거나 2등 = 3등 = 0인 경우이다.

 

1등 = 2등이라면 $S_S[i] \ne S_H[i]$인 모든 인덱스 $i$에서 $S_S[i] = S_K[i]$라는 의미이다. 앞에서 처리한 케이스를 제외하면 1등 = 2등 >= 2임이 보장되고, $S_S \ne S_K$이니 $S_S[i] \ne S_K[i]$인 $i$가 적어도 하나 있으며, 이때 $S_S[i] = S_H[i]$이다. 따라서 현재 정답 문자열에서는 이러한 $i$에서 누구도 점수를 얻지 못하니 정답 문자열의 $i$번째 문자를 $S_S[i]$로 바꾸면 1등, 3등의 점수가 1 증가하고, 결국 1등 > 2등 >= 2 > 3등 = 1이 되니 조건을 만족한다.

 

2등 = 3등 = 0이라면 3등의 점수를 유지한 채 2등의 점수를 1 올려야 하며, 두 가지 방법이 있다.

• 아무도 점수를 얻지 못하는 인덱스에서 점수 얻기
• 1등이 점수를 얻은 인덱스에서 점수 얻기

아무도 점수를 얻지 못한 인덱스는 $S_S[i] = S_H[i]$이다. 따라서 이러한 인덱스 중 $S_K[i] \ne S_H[i]$인 $i$를 사용하면 2등의 점수만 1 증가하며, 1등 >= 2이므로 1등 >= 2 > 2등 = 1 > 3등 = 0이 되어 조건을 만족한다.

 

이러한 인덱스가 없다면, 1등의 점수를 1 뺏어와야 한다. 따라서 1등 = 2라면 조건을 만족시킬 수 없으며, 1등 > 2라면 $S_K[i] \ne S_H[i]$인 $i$를 하나 골라 사용하여 1등 > 2등 = 1 > 3등 = 0 조건을 맞출 수 있다. $S_K \ne S_H$이므로 이러한 인덱스 $i$는 항상 존재한다.

 

하머리아파

출제자 풀이는 아마 케웍을 좀 줄이고 나이브 탐색이 좀 들어간 것 같다

#include <bits/stdc++.h>
using namespace std;
 
void NO(){
    cout << -1;
    exit(0);
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    string S, K, H, ans;
    int N, ss = 0, sk = 0;
    cin >> N >> S >> K >> H;
    if (S == K or K == H or S == H)
        NO();
    for (int i = 0; i < N; i++){
        if (S[i] == H[i]) {
            char c = 'a';
            for (; c == S[i] or c == K[i] or c == H[i]; c++);
            ans.push_back(c);
        }
        else{
            ans.push_back(S[i]);
            ss++;
            if (S[i] == K[i]) sk++;
        }
    }
    if (ss == 1) NO();
    if (sk == 0){
        int chk = 0;
        for (int i = 0; i < N; i++){
            if (K[i] != H[i] and H[i] == S[i]){
                ans[i] = K[i];
                chk = 1;
                break;
            }
        }
        if (!chk and ss <= 2) NO();
        if (!chk){
            for (int i = 0; i < N; i++){
                if (K[i] != H[i]){
                    ans[i] = K[i];
                    break;
                }
            }
        }
    }   
    else if (ss == sk){
        for (int i = 0; i < N; i++){
            if (S[i] != K[i]){
                ans[i] = S[i];
                break;
            }
        }
    }
    cout << ans;
}