문제
백준 25421 조건에 맞는 정수의 개수 : https://www.acmicpc.net/problem/25421
양의 정수 n이 주어진다. 아래 조건을 만족하는 양의 정수 A의 개수를 구하자.
정수 A는 n개의 자릿수를 갖는 정수이며, 각각의 자릿수는 0이 아니다.
정수 A의 이웃한 두 자리의 숫자의 차이는 2 이하이다. 즉, 정수 A의 각 자리의 숫자를 높은 자릿수부터 낮은 자릿수 순서로 A1, A2, ..., An이라고 할 때, |Ai - Ai+1| ≤ 2 (1 ≤ i ≤ n-1) 이다.
입력
첫 번째 줄에 양의 정수 n이 주어진다.
출력
첫 번째 줄에 양의 정수 A의 개수를 987,654,321로 나눈 나머지를 출력한다.
예제 입력 1
1
예제 출력 1
9
1개의 자릿수를 갖는 양의 정수 1, 2, 3, ..., 9가 A에 해당된다. 따라서 정답은 9이다.
예제 입력 2
2
예제 출력 2
39
2개의 자릿수를 갖고 첫 번째 자리의 숫자와 두 번째 자리의 숫자의 차이가 2보다 작거나 같은 양의 정수 11, 12, 13, 21, 22, 23, 24, 31, 32, ... , 97, 98, 99가 A에 해당된다. 따라서 정답은 39이다.
예제 입력 3
100
예제 출력 3
736753518
풀이
해당 문제는 전형적인 dp의 문제이다 길이 i의 문자열의 마지막 자리수가 n으로 끝나는 갯수는
길이 i-1의 문자열의 마지막 자리수가 n+2보다 작거나 같고 n-2보다 크거나 같은 갯수의 합이다.
점화식으로는
dp[i][n]=dp[i-1][n-2]+dp[i-1][n-1]+dp[i-1][n]+dp[i-1][n+1]+dp[i-1][n+2]
이다.
이때 n이 0보다 크고 10보다 작을때만 계산하자.
코드
import java.util.Scanner;
public class BOJ25421 {
public static void main(String args[]){
int n=new Scanner(System.in).nextInt();
int dp[][]=new int[n][10];
for(int i=1;i<10;i++){
dp[0][i]=1;
}
for(int i=1;i<n;i++){
for(int j=1;j<10;j++){
int t=0;
for(int k=j-2;k<=j+2;k++){
if(k>0&&k<10){
t+=dp[i-1][k];
t%=987654321;
}
}
dp[i][j]=t;
}
}
int ans=0;
for(int i=0;i<10;i++){
ans+=dp[n-1][i];
ans%=987654321;
}
System.out.println(ans);
}
}
후기
요정도 DP는 이제 그냥 보자마자 푸는구만 ㅎㅎ 좋아 좋아
