코딩테스트에 대비하기 위한 여러 가지 알고리즘 문제를 풀어보며 실제 시험에서의 문제 해결 능력을 키워봅시다.
문제 설명
계단 수는 다음과 같은 규칙을 따릅니다. n자리 수이며, 각 자리 숫자는 오름차순으로 증가해야 합니다. 즉, 인접한 두 자리 수의 차이는 정확히 1이어야 합니다. 예를 들어, 123, 234, 345는 모두 계단 수입니다.
문제
N이 주어질 때, N자리 계단 수의 개수를 구하는 프로그램을 작성하세요.
입력
- 첫 번째 줄에 자연수 N이 주어집니다. (1 ≤ N ≤ 100)
출력
- N자리 계단 수의 개수를 10007로 나눈 나머지를 출력합니다.
예제 입력
3
예제 출력
14
설명
N이 3이면, 3자리 계단 수는 123, 132, 210, 321, 234, 345, 456, 567, 678, 789 등 총 14개가 존재합니다.
문제 풀이 과정
이 문제를 해결하기 위해서는 다이나믹 프로그래밍(Dynamic Programming)의 기법을 사용할 수 있습니다.
계단 수는 이전 N-1자리 수를 기반으로 한 N자리 수의 조합으로 생각할 수 있습니다. N-1자리 수의 마지막 숫자에 따라 N자리 수의 마지막 숫자가 결정되므로, 이를 고려하여 DP 배열을 업데이트하면 됩니다.
풀이 접근 방식
- 상태 정의: dp[n][last]를 n자리 계단 수 중 마지막 자리 수가 last인 경우의 개수로 정의합니다. n은 자리 수를 의미하며, last는 마지막 숫자(0~9)를 의미합니다.
- 초기 상태 설정: 1자리 수의 경우(즉, N=1일 때) 각 숫자(1~9)는 각기 1개의 경우의 수를 가집니다. 따라서 dp[1][1] ~ dp[1][9]는 1, dp[1][0]는 0입니다.
-
상태 전이: n자리 수는 n-1자리 수에서 만들어집니다. 마지막 숫자가 last일 때, 마지막 숫자는 last-1 또는 last+1일 수 있습니다. 이를 수식으로 표현하면 다음과 같습니다.
dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]여기서 last는 1부터 8까지의 범위를 가질 수 있습니다(0과 9는 각각 한쪽에 한정되므로).
- 결과 계산: N자리 수의 개수는 dp[N][0] + dp[N][1] + … + dp[N][9]의 합입니다. 그러나 문제에서 요구하는 것은 10007로 나눈 나머지이므로, 계산 과정에서 이 연산을 수행해야 합니다.
자바 코드 구현
import java.util.Scanner;
public class StairNumber {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int MOD = 10007;
// DP 배열 초기화
int[][] dp = new int[N + 1][10];
// 1자리 수 초기화
for (int i = 1; i < 10; i++) {
dp[1][i] = 1;
}
// DP 테이블 구성
for (int n = 2; n <= N; n++) {
for (int last = 0; last <= 9; last++) {
if (last > 0) { // last가 0이 아닐 경우
dp[n][last] += dp[n - 1][last - 1];
}
if (last < 9) { // last가 9가 아닐 경우
dp[n][last] += dp[n - 1][last + 1];
}
dp[n][last] %= MOD; // MOD 연산
}
}
// 결과 합산
int result = 0;
for (int last = 0; last <= 9; last++) {
result = (result + dp[N][last]) % MOD;
}
// 결과 출력
System.out.println(result);
sc.close();
}
}
예시
입력
3
출력
14
위의 코드를 실행하게 되면, 3자리 계단 수의 개수를 정확하게 구할 수 있습니다.
추가 사항
문제를 해결하고 난 후, 다양한 테스트 케이스로 알고리즘의 정확성을 검증하는 것이 중요합니다. 또한 코드를 최적화하거나 다양한 방법으로 알고리즘을 접근하여 그 결과를 비교하는 것도 좋은 방법입니다.
마지막으로, 다이나믹 프로그래밍 문제는 많은 경우 그래프 이론과도 연결될 수 있으니, 항상 이러한 관점을 갖고 문제를 푸셔야 합니다.