[백준 10844 : 쉬운 계단 수] DP, Java

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

10844번: 쉬운 계단 수

문제 요약 : 길이가 N인 수 중, 계단수가 총 몇 개인지 구하는 문제 
dp[n][i] : 길이가 n인 수에서 i가 마지막에(n번째에) 들어갈 때, 그 수가 계단수가 되는 경우의 수

 

처음에는 1차원 dp 배열로 풀이 하려고 했는데 길이도 따져야 하고 이전 수와의 관계도 따져야 해서 헤매다가 2차원으로 구현하게 되었다. 어렵다=__=;

 

dp[n][i] = dp[n-1][i-1]+dp[n-1][i+1]의 의미는 다음과 같다.

 

길이가 n인 숫자의 제일 마지막에 i가 온 상태에서 그 수가 계단수가 되기 위해서는

바로 전 숫자(n-1번째 수)의 크기가 i보다 1이 크거나 1이 작아야 한다.

 

이해를 위해 간단한 예시를 들어보자면,

dp[2][2]인 경우는 2로 끝나는 두 자리 수이다.

이런 경우 계단수가 되려면 1 2 이거나 3 2 가 되어야 한다.

즉 앞자리 수가 2보다 1이 작거나 1이 커야 하는 것이다.

( dp[1][1]+dp[1][3] 으로 계산해보면 2가지 경우의 수가 나온다. )

 

dp[3][2]같은 경우는

2 1 2,  2 3 2, 4 3 2 가 가능하다.(0 1 2는 문제에서 0으로 시작하지 않는다고 언급했기 때문에 제외됨)

dp[3][2] = dp[2][1]+dp[2][3]이고 또 전개해보면

dp[1][0]+dp[1][2]+dp[1][2]+dp[1][4]로 경우의 수가 세 가지 나온다.

 

그리고 제출하기 전에 범위를 유의하길 바란다!

1000,000,000으로 나눠주는거 때문에 '틀렸습니다'를 엄청 많이 보고서야 맞출 수 있었다..-ㅠ-웩

import java.util.Scanner;

public class boj10844 {
static int[][]d;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);

int n = scan.nextInt();
d = new int[n+1][11];

d[1][0] = 0; //0으로 시작하는 경우는 없다

for(int j=1;j<=9;j++)
d[1][j] = 1;

for(int i=2;i<=n;i++) {
for(int j=0;j<=9;j++) {
if(j==0)
d[i][j] = d[i-1][j+1]%1000000000;
else if(j==9)
d[i][j] = d[i-1][j-1]%1000000000;
else
d[i][j] = (d[i-1][j-1]+d[i-1][j+1])%1000000000;

//System.out.println("test d["+i+"]["+j+"] = "+d[i][j]);
}
}
long sum = 0;

for(int j=0;j<=9;j++) {
sum += d[n][j];
}
System.out.println(sum%1000000000);
}
}