[백준] 25421 : 조건에 맞는 정수의 개수 - JAVA

문제

https://www.acmicpc.net/problem/25421

25421번: 조건에 맞는 정수의 개수

 

풀이

내가 안좋아하는 DP 문제였다. 그래서 그런지 풀이를 생각하는데 오래 걸렸다. (어려운 DP...)

 

문제는 매우 단순하다. n 자릿수인 숫자에 대해 각자리수가 0이 아니고 이웃한 숫자끼리 2 이하의 차이만 나는 숫자의 개수를 구하는 문제였다. 

 

dp 배열을 설정하는데 어려움을 겪었는데 맨 앞자리수를 기준으로 하려고 해서 어려움을 겪었다.

dp[숫자의 길이][끝자리 숫자] 로 설정하면 된다.

 

예를 들어 보자.

n = 2일 때 숫자들은 끝자리 수에 대해 숫자들은 다음과 같이 나온다

1	2	3	4	5	6	7	8	9
11 21 31	12 22 32 42	13 23 33 43 53	24 34 44 54 64	35 45 55 65 75	46 56 66 76 86	57 67 77 87 97	68 78 88 98	79 89 99

n=3일때 끝자리수가 1인것에 대해서는 다음과 같이 나온다.

111 211 311

121 221 321 421

131 231 331 431 531

규칙이 보인다.

dp[3][1] = dp[2][1] + dp[2][2] + dp[2][3]

즉, 끝자리수를 제외하고 나머지 두자리수에 대해 나오는 경우의 수를 더해주면 세자릿 수에 대해 나온다.

그리고 이 나머지 두자리수는 n=2일때에서 가져오면 되는데 이때 10의 자리수가 1의 자리수와 2이하 차이가 나는것ㄱ만 가져온다. 

 

따라서 dp식은 다음과 같이 나온다.

dp[i][j] = dp[i-1][j-2]+dp[i-1][j-1]+dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j+2]

 

코드

import java.io.*;
import java.util.*;

class Main {	
	
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		int n = Integer.parseInt(br.readLine());
		
		long dp [][] = new long [n+1][10];
		
		for(int i=1;i<=9;i++) {
			dp[1][i] = 1;
		}
		
		for(int i=2;i<=n;i++) { //길이
			for(int j=3;j<=7;j++) {
				dp[i][j] = (dp[i-1][j-2]+dp[i-1][j-1]+dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j+2])%987654321;
			}
			dp[i][1] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][3])%987654321;
			dp[i][2] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4])%987654321;
			dp[i][8] = (dp[i-1][6] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9])%987654321;
			dp[i][9] = (dp[i-1][7] + dp[i-1][8] + dp[i-1][9])%987654321;
		}
				
		long sum = 0;
		for(int i=1;i<=9;i++) {
			sum += dp[n][i];
		}
		
		System.out.println(sum%987654321);
		
	}
	
}

 

 

dp는 많이 풀어야 될것 같다...(dp는 너무 싫다...)