2016.05.12 모임 54

모임 공지

• 활동 일시: 05월 12일 (목) 19:02
• 모임 장소: 하이퍼 커넥트 14층
• 활동 주제: google codejam 2016 Round 1B, 1C
• 샌드위치 형성

장소는 이곳을 참고 하세요

google codejam 2016 Round 1B

Problem A. Getting the Digits

문제링크
"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"
어떤 숫자에 대해 그 숫자에만 존재하는 알파벳을 먼저 찾으면 된다.
예를 들면, ‘Z’ 는 0 에만 있다.

따라서 우선 ‘Z’, ‘X’, ‘U’, ‘W’, ‘G’ 를 검사하면 된다. 이것들은 각각 0, 6, 4, 2, 8 에만 존재하는 글자이다.
이제 남은 글자에 대해서도 같은 방법을 사용하면 된다.
따라서 다음과 같은 순서대로 검사를 하면 greedy 로 문제를 해결할 수 있다.

'Z', 'X', 'U', 'W', 'G', 'F', 'H', 'O', 'S', 'N'
0, 6, 4, 2, 8, 5, 3, 1, 7, 9

소스코드 :

const string STR [] = {
    "ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"
};
char cc [] = { 'Z', 'X', 'U', 'W', 'G', 'F', 'H', 'O', 'S', 'N' };
char ii [] = { 0, 6, 4, 2, 8, 5, 3, 1, 7, 9 };

void solve() {
    multiset<char> s;
    vector<int> out;

    string in; cin >> in;
    for (char c : in) s.insert(c);

    for (int i = 0; i < 10; i++) {
        while (s.find(cc[i]) != s.end()) {
            out.push_back(ii[i]);
            for (char c : STR[ii[i]]) {
                s.erase(s.find(c));
            }
        }
    }

    sort(out.begin(), out.end());
    for (int i : out) cout << i;
    cout << endl;
}

Problem B. Close Match

문제링크

문제 설명 : 두 개 수가 주어진다. 다음 조건을 만족하게 ? 를 임의의 숫자로 바꾸어 두 수를 출력한다.

1. 두 수의 차가 가능한 작게
2. 가능한 첫 번째 숫자가 작게
3. 가능한 두 번째 숫자가 작게

알고리즘 :

1. 가능한 두 수가 같게 한다
2. 두 수 중 하나 이상 ? 가 나오면 : 두 수가 같거나, 차가 1 인 경우를 다 검사한다.
3. 두 수가 앞 자리에서 다르게 되었다면 큰 수는 최대한 작게, 작은 수는 최대한 크게 결정한다.

얼핏 경우의 수가 3배씩 증가할 거 같지만 그렇지 않다.
왜냐하면 한 번 두 수의 대소가 정해지면 그 이후엔 greedy 가 되기 때문이다.

사진