[백준] 10844번 쉬운 계단수 어떻게 풀 수 있을까?
1. 문제
1) 링크
2) 문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
3) 입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
4) 출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
더 자세한 문제의 제한은 위의 링크에 들어가서 확인해보자.
2. 풀이
이 문제는 자릿수를 하나씩 줄여서 풀어볼 수 있다.
만약 자릿수가 n이었고 수가 연속해야 하기 때문에 마지막 숫자가 a였다면 그 전 수는 자릿수 n-1에 마지막 수가 a-1 또는 a+1이었을 것이다. 즉 이처럼 역으로 생각해서 하나씩 자리수를 줄여본다.
다시 말해 이 문제는 자리수가 큰 문제에서 작은 문제로 나누어서 푸는 다이나믹 프로그래밍 관련 문제이다.
즉 우리는 여기서 2차원 배열을 정의하고 앞의 배열은 자리수, 뒤의 배열은 마지막 자리 수를 나타내는 용도로 사용하기로 하자.
ans[n][i] 가 있다면 n은 n자리 자릿수를 나타내는 것이고 i는 마지막에 사용된 숫자 (1~9까지) 나타내는 것이다.
그럴 때 ans[n][i]= ans[n-1][i-1] + ans[n-1][i+1]이라고 할 수 있다.
하지만 여기서 한 가지 주의해야 할 점은 마지막 자리의 숫자가 0이거나 9인 경우 그것보다 더 작고, 큰 숫자가 없으므로 이 경우는 예외처리를 해 주어야 한다는 점이다.
그리고 이러한 문제는 항상 초기값 starting point가 필요한데 이 경우 자릿수의 최소 자리는 1자리 임으로 n의 starting point는 1이라고 할 수 있다. n이 1일 경우 마지막 자리의 수는 곧 가장 높은 자리를 의미하기 때문에 0이 들어갈 수 없다는 것을 조심해야 한다.
이 경우에는 i가 1부터 9까지인 경우에만 1이라고 처리해주면 된다.
3. 코드
전체코드를 살펴보면 아래와 같다.
import java.util.*;
public class Main{
public static long mod = 1000000000L;
static long[][] ans;
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
int n=sc.nextInt();
ans=new long[n+1][10]; //계단의 길이, 마지막 숫자
for(int i=1; i<=9; i++){
ans[1][i]=1; //초기값 설정. 계단의 길이가 1이고 마지막 자리가 i인것은 다 한개
}
for(int i=2; i<=n; i++){
for(int j=0; j<=9; j++){
if (j>=1){
ans[i][j]+=ans[i-1][j-1]; //하나 작은 것과 인접
}
if (j<=8){
ans[i][j]+=ans[i-1][j+1]; //하나 큰 것과 인접
}
ans[i][j]%=mod;
}
}
long fin_ans=0;
for(int i=0; i<=9; i++){
fin_ans+=ans[n][i];
}
System.out.println(fin_ans%mod);
}
}여기서 숫자가 너무 커질 것을 염려해 mod로 매번 나머지 연산을 해주어야 된다는 점을 까먹지 말자. mod를 여러번 사용해야 하니 계속 숫자를 사용하기 보다는 static 변수로 만들어 이를 여러번 활용하자