14174 Block Game

N개의 팻말의 양면에 단어가 하나씩 적혀있다.

이 팻말은 앞면, 혹은 뒷면만 사용할 수 있는데 각 단어를 표시하기 위해서는 단어를 구성하는 알파벳 블록이 필요하다.

예를들어 "cat"를 표시하려면 c = a = t = 1개씩 필요하다.

이때 가능한 모든 경우를 표시하기 위해서 필요한 알파벳 블록 최소값을 구해야 한다.

해법

모든 경우를 따지자면 2^N인데 N이 최대 100이라 이건 안된다. 다른 방법을 생각해보면

i번째 팻말을 표시할 때 필요한 블록의 개수가

i번째 팻말의 앞 : cnt[0]['a'] cnt[0]['b'] .... cnt[0]['z']

i번째 팻말의 뒤 : cnt[1]['a'] cnt[1]['b'] .... cnt[1]['z']

이라고 할 때 어떤 경우에도 i번째 팻말을 표시할 수 있으려면 필요한 알파벳 블록의 갯수는

cnt[alphabet] = max(cnt[0][alphabet], cnt[1][alphabet])

이다. 따라서 팻말별로 앞뒤로 필요한 알파벳 블록을 구해놓고 둘중 더 큰값을 최종 결과에 더해나가면 최악의 경우에도 모두 표시 할 수 있다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, ans[26];
 
int main() {
    scanf("%d", &n);
    while (n--) {
        char s[2][11];
        int cnt[2][26] = { 0, };
        for (int i = 0; i < 2; ++i) {
            scanf(" %s", s[i]);
            for (int j = 0; s[i][j]; ++j) cnt[i][s[i][j] - 'a']++;
        }
        for (int i = 0; i < 26; ++i) ans[i] += max(cnt[0][i], cnt[1][i]);
    }
    for (int i = 0; i < 26; ++i) printf("%d\n", ans[i]);
    return 0;
}