백준 - 사전 (1256)

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var (N, M, K) = (input[0], input[1], input[2])

var dp = Array(repeating: Array(repeating: 0, count: 201), count: 201)

// dp 테이블 초기화
for i in 1...200 {
    dp[i][0] = 1
    dp[i][1] = i
    dp[i][i] = 1
}

// dp 테이블 채우기
for i in 2...200 {
    for j in 1...i {
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        if dp[i][j] > 1000000000 {
            dp[i][j] = 1000000001
        }
    }
}

if dp[N + M][N] < K {
    print("-1")
} else {
    findAnswer()
}

func findAnswer() {
    var answer = ""
    
    while N > 0 && M > 0 {
        if dp[N - 1 + M][M] >= K {
            answer += "a"
            N -= 1
        } else {
            answer += "z"
            K -= dp[N - 1 + M][M]
            M -= 1
        }
    }
    while N != 0 {
        answer += "a"
        N -= 1
    }
    while M != 0 {
        answer += "z"
        M -= 1
    }
    
    print(answer)
}

전체 경우의 수 구하는 방법

문자열에 나오는 문자가 ‘a’, ‘z’ 밖에 없기 때문에 전체 문자열 종류의 개수는 a와 z의 개수 (N + M) 에서 a(N) 를 고르는 경우의 수와 같다.

즉 a가 몇 번째 자리에 올 건지를 고르는 것과 같다. (a a _ _ , a _ a _ , a _ _ a …)

K번째 문자열 찾는 방법

K번째 문자열을 찾는 데에도 위의 아이디어가 사용된다.

첫 번째 자리의 문자를 a 로 선택했다면 나머지 자리 문자열의 종류는 나머지 a와 z의 개수 (N - 1 + M) 에서 z(M) 을 고르는 경우의 수와 같다.

이 경우의 수가 K보다 크거나 같다면 a 를 선택하고, 그렇지 않다면 z 를 선택한 다음 K의 값을 여기서 구한 경우의 수만큼 빼준다.

이 과정을 반복하다가 a나 z 중 하나라도 다 쓴 문자가 있다면 남은 문자들을 뒤에 바로 붙여준다.

순열의 순서와 경우의 수를 찾는 아이디어가 비슷한 것 같다.

주의할 점

dp 테이블에 조합 경우의 수들을 모두 저장하다보면 오버플로우가 발생한다.

따라서 경우의 수가 K의 최댓값(1,000,000,000)보다 커지면 그냥 이 값보다 큰 값을 아무거나 넣어준다. 어차피 K보다 작은지 아닌지만 비교하기 때문에 정확한 경우의 수를 구하지 않아도 됨!