1. 카멜 케이스와 스네이크 케이스 변환 알고리즘

프로그래밍에서 자주 사용되는 두 가지 명명 규칙인 카멜 케이스(CamelCase)와 스네이크 케이스(snake_case) 간의 변환을 처리하는 문제입니다. 문제의 핵심은 입력받은 문자열이 유효한 형식인지 판단하고, 카멜 케이스인 경우에만 스네이크 케이스로 변환하는 것입니다.

변환 및 판별 규칙

• 카멜 케이스: 첫 번째 단어는 소문자로 시작하며, 이후 단어의 첫 글자만 대문자로 표기합니다 (예: myName).
• 스네이크 케이스: 모든 단어는 소문자이며, 단어 사이를 언더스코어(_)로 구분합니다 (예: my_name).
• 불확실한 상태 (indistinct): 다음과 같은 경우는 유효하지 않은 형식으로 간주합니다.
  • 대문자로 시작하거나 언더스코어로 시작/종료되는 경우
  • 언더스코어가 연속으로 사용된 경우
  • 대문자와 언더스코어가 혼용된 경우

#include <iostream>
#include <string>
#include <vector>
#include <cctype>

using namespace std;

void processString() {
    int n;
    if (!(cin >> n)) return;
    
    while (n--) {
        string s;
        cin >> s;
        
        // 기본 예외 처리: 첫 글자가 대문자이거나 언더스코어인 경우, 또는 마지막이 언더스코어인 경우
        if (isupper(s[0]) || s[0] == '_' || s.back() == '_') {
            cout << "indistinct" << endl;
            continue;
        }
        
        string result = "";
        bool hasUpper = false;
        bool hasUnderscore = false;
        bool isInvalid = false;
        
        for (int i = 0; i < s.length(); ++i) {
            if (isupper(s[i])) {
                // 카멜 케이스와 스네이크 케이스가 혼용된 경우 체크
                if (hasUnderscore) {
                    isInvalid = true;
                    break;
                }
                hasUpper = true;
                result += '_';
                result += (char)tolower(s[i]);
            } else if (s[i] == '_') {
                // 연속된 언더스코어 또는 카멜 케이스와의 혼용 체크
                if (hasUpper || (i > 0 && s[i-1] == '_')) {
                    isInvalid = true;
                    break;
                }
                hasUnderscore = true;
                result += s[i];
            } else {
                result += s[i];
            }
        }
        
        if (isInvalid) {
            cout << "indistinct" << endl;
        } else {
            cout << result << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    processString();
    return 0;
}

2. 상태 압축 DP를 이용한 조건부 순열 계산

N개의 집이 있고 각 집마다 고유의 가치가 있을 때, 인접한 두 집의 가치가 서로 약수 혹은 배수 관계(정수 배)여야 한다는 조건 만족하는 순열의 수를 구하는 문제입니다. N의 범위가 최대 15로 작기 때문에 비트마스킹(Bitmasking)을 활용한 동적 계획법(DP)으로 해결할 수 있습니다.

알고리즘 설계

dp[mask][last]를 현재 선택된 집들의 집합이 mask이고, 마지막으로 배치된 집의 인덱스가 last인 경우의 수라고 정의합니다.

• 상태 전이: 현재 상태에서 아직 선택되지 않은 집 next를 추가할 때, houses[last] % houses[next] == 0 또는 houses[next] % houses[last] == 0 조건을 만족하면 상태를 갱신합니다.
• 시간 복잡도: O(2^N * N^2)으로, N=15일 때 충분히 제한 시간 내에 계산이 가능합니다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef long long ll;

void solveHousePermutation() {
    int n;
    if (!(cin >> n)) return;
    
    vector<int> values(n);
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
    }
    
    // dp[mask][last_index]
    // mask: 방문한 집들의 비트 집합, last_index: 마지막으로 놓인 집의 번호
    static ll dp[1 << 15][15];
    memset(dp, 0, sizeof(dp));
    
    // 기저 상태: 집 하나를 고르는 경우
    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = 1;
    }
    
    // 모든 상태 탐색
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int last = 0; last < n; ++last) {
            if (!(mask & (1 << last)) || dp[mask][last] == 0) continue;
            
            for (int next = 0; next < n; ++next) {
                // 이미 방문했거나 조건을 만족하지 않는 경우 제외
                if (mask & (1 << next)) continue;
                
                if (values[last] % values[next] == 0 || values[next] % values[last] == 0) {
                    dp[mask | (1 << next)][next] += dp[mask][last];
                }
            }
        }
    }
    
    ll totalWays = 0;
    int fullMask = (1 << n) - 1;
    for (int i = 0; i < n; ++i) {
        totalWays += dp[fullMask][i];
    }
    
    cout << totalWays << endl;
}

int main() {
    solveHousePermutation();
    return 0;
}