백준 1010번: 다리 놓기 - Kotlin 풀이 🚀
1. 문제 소개 📝
재원이는 다리가 없어서 시민들이 강을 건너는 데 불편을 겪고 있습니다. 그래서 강의 서쪽과 동쪽에 있는 사이트를 최대한 많이 연결하는 다리를 짓기로 했습니다. 한 사이트에는 최대 한 개의 다리만 연결될 수 있으며, 다리끼리는 서로 겹쳐질 수 없습니다. 이때 다리를 지을 수 있는 경우의 수를 구하는 문제입니다.
🔹 입력 형식
- 첫 번째 줄: 테스트 케이스의 개수 T
- 각 테스트 케이스:
- 첫 번째 줄: 서쪽 사이트의 개수 N, 동쪽 사이트의 개수 M (0 < N ≤ M < 30)
🔹 출력 형식
각 테스트 케이스에 대해 다리를 지을 수 있는 경우의 수를 출력합니다.
2. 문제 해결 접근법 💡
이 문제는 기본적으로 **조합** 문제입니다. 서쪽의 사이트에서 동쪽의 사이트로 다리를 짓는 방법은 `M`개의 사이트에서 `N`개의 사이트를 선택하는 방법과 동일합니다. 이를 수학적으로 표현하면, `C(M, N)` (즉, M에서 N을 고르는 경우의 수)로 구할 수 있습니다.
🔹 조합 공식
조합의 개수는 아래와 같이 계산할 수 있습니다:
C(M, N) = M! / (N! * (M - N)!)이때, 팩토리얼 계산을 단순하게 반복문을 통해 구현할 수도 있지만, 동적 프로그래밍(DP)을 사용하여 계산을 효율적으로 최적화할 수 있습니다.
3. Kotlin 코드 구현 💻
fun combination(n: Int, r: Int): Long {
if (r == 0 || r == n) return 1
val dp = Array(n + 1) { LongArray(r + 1) }
// 기본값 설정
for (i in 0..n) {
dp[i][0] = 1
}
// DP 배열 채우기
for (i in 1..n) {
for (j in 1..r) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
}
}
return dp[n][r]
}
fun solve() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
println(combination(m, n))
}
fun main() {
val t = readLine()!!.toInt()
repeat(t) {
solve()
}
}
4. 코드 설명 🧐
- 동적 프로그래밍 배열 초기화:
combination(n, r)함수에서는 동적 프로그래밍(DP)을 활용하여 조합을 계산합니다. 먼저 DP 테이블을 생성하고, 기본값을 설정합니다. 조합의 기본 규칙에 의해dp[i][0] = 1로 설정됩니다. - DP 배열 채우기:
이후,
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]규칙에 따라 테이블을 채웁니다. 이 관계는 이전 값들을 기반으로 현재 값을 계산합니다. - 입력 처리:
각 테스트 케이스에 대해 서쪽의 사이트 개수 N과 동쪽의 사이트 개수 M을 입력받고, 그에 해당하는 조합 수를 출력합니다.
- 메인 함수:
main()함수는 테스트 케이스의 개수 T를 입력받고, 각 테스트 케이스에 대해solve()함수를 호출하여 결과를 출력합니다.
5. 성능 분석 ⏱️
| 접근법 | 시간 복잡도 |
|---|---|
| 동적 프로그래밍을 이용한 조합 계산 | O(N * R) (DP 테이블을 채우는 시간 복잡도) |
문제의 조건에서 주어진 최대 값인 N, M (0 < N ≤ M < 30)에 대해서는 충분히 효율적으로 계산할 수 있습니다. DP 방식으로 계산하면, O(N * R)로 해결할 수 있기 때문에 매우 효율적으로 작동합니다.
6. 결론 🎯
이 문제는 **조합** 문제로, 서쪽의 사이트와 동쪽의 사이트에서 다리를 최대한 많이 건설하는 경우의 수를 구하는 문제입니다. Kotlin에서 동적 프로그래밍을 사용해 효율적으로 문제를 해결할 수 있었습니다. DP를 활용하여 문제를 풀 수 있는 좋은 경험이었습니다. 🚀
다음에도 다른 알고리즘 문제를 풀어보겠습니다! 😊