오늘은 코틀린을 사용하여 ‘계단 수 구하기’라는 흥미로운 알고리즘 문제를 해결해보겠습니다. 본 강좌에서는 문제의 정의, 규칙, 해결 전략 및 코드를 구현하는 과정까지 자세히 설명하겠습니다. 다루는 내용은 다음과 같습니다.
1. 문제 정의
계단 수는 수의 자릿수에 따라 정의되는 수로, 각 자리의 수는 다음과 같은 규칙을 따릅니다:
- 맨 마지막 자리의 수와 그 앞 자리의 수 차이가 1이어야 합니다.
- 예를 들어, 123, 321, 456은 계단 수입니다. 그러나 122, 200, 300은 계단 수가 아닙니다.
주어진 정수 N이 있을 때, N자리로 이루어진 계단 수의 개수를 구하는 문제입니다. 입력값 N을 고려하여 출력값을 계산하는 방식을 설명하겠습니다.
2. 문제 규칙
– 입력 최대 자리 수는 100이며, N이 1일 경우에는 0에서 9까지의 수를 포함하여 10개의 계단 수가 존재합니다.
– 각 자리 수를 0에서 9까지의 숫자로 고려할 수 있으며, 첫 자리 수는 0이 될 수 없습니다.
– 자리 수가 증가함에 따라 계단 수의 조합 가능성이 증가합니다.
3. 해결 전략
이 문제는 동적 프로그래밍을 통해 해결할 수 있습니다. 기본 아이디어는 자릿수 별로 가능한 계단 수의 개수를 저장하고 이를 기반으로 다음 자릿수의 계단 수 개수를 계산하는 것입니다.
- 각 자릿수에 대해 가능한 마지막 숫자를 고려하여 이전 자릿수에서의 값을 통해 새로운 값을 계산합니다.
- 예를 들어,
dp[n][digit]는 n자리 수에서 마지막 숫자가digit일 때 계단 수의 개수를 저장하는 배열입니다. - 따라서
dp[n][digit]는dp[n-1][digit-1]와dp[n-1][digit+1]의 합으로 구할 수 있습니다.
3.1. 점화식
아래와 같은 점화식을 통해 dp 배열을 구성해 나갈 수 있습니다.
dp[n][0] = dp[n-1][1]
dp[n][9] = dp[n-1][8]
dp[n][digit] = dp[n-1][digit-1] + dp[n-1][digit+1] (1 <= digit <= 8)
4. 코드 구현
이제 문제 해결을 위한 코드를 구현해 보겠습니다. 아래는 코틀린을 사용한 코드입니다.
fun countStairNumbers(n: Int): Int {
if (n == 1) return 10 // N이 1일 때 계단 수는 0~9까지
val mod = 1000000000 // 결과를 출력할 때 사용하는 모듈러 연산
val dp = Array(n + 1) { IntArray(10) }
// 초기값 설정
for (j in 1..9) {
dp[1][j] = 1 // 첫 자리 숫자는 1~9까지
}
// DP 배열 구성
for (i in 2..n) {
for (j in 0..9) {
if (j == 0) {
dp[i][j] = dp[i - 1][1] // 0은 이전 자리의 1에서만 가능
} else if (j == 9) {
dp[i][j] = dp[i - 1][8] // 9는 이전 자리의 8에서만 가능
} else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod
}
}
}
// 총 계단 수 계산
var result = 0
for (j in 0..9) {
result = (result + dp[n][j]) % mod
}
return result
}
fun main() {
val n = readLine()!!.toInt() // 입력값 받기
println(countStairNumbers(n)) // 계단 수 출력
}
5. 실행 및 결과
위 코드를 실행하면 입력된 N값에 따라 계단 수의 개수가 출력됩니다. 아래는 몇 가지 테스트 케이스에 대한 결과입니다.
- 입력: 1 → 출력: 10
- 입력: 2 → 출력: 17
- 입력: 3 → 출력: 32
각 입력값에 대해 계단 수의 개수가 잘 계산되는 것을 확인할 수 있습니다.
6. 결론
본 강좌에서 우리는 ‘계단 수 구하기’ 문제를 해결하기 위해 동적 프로그래밍을 활용했습니다. 문제 해결 과정에서 점화식과 DP 배열을 구성하는 방법을 살펴보았고, 이를 통해 실제 코드를 작성해보았습니다. 이러한 문제들은 코딩 테스트에서 자주 출제되므로 충분한 연습을 통해 익히는 것이 중요합니다.
앞으로도 다양한 알고리즘 문제를 다루어 볼 예정이며, 코틀린을 통한 문제 해결 능력을 키우는 데 도움이 되기를 바랍니다. 감사합니다!