[java] 10844 쉬운 계단 수

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

package backjoon_10844;
import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int l = Integer.parseInt(br.readLine());
        long[][] dp = new long[l+1][10];
        for(int i =1; i<=9; i++) {
            dp[1][i] = 1;
        }
         for (int i = 2; i <= l; i++) {
                for (int j = 0; j <= 9; j++) {
                    if (j == 0) {
                        dp[i][0] = dp[i-1][1] % 1_000_000_000;
                    } else if (j == 9) {
                        dp[i][9] = dp[i-1][8] % 1_000_000_000;
                    } else {
                        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1_000_000_000;
                    }
                }
        }
         
        long result = 0;
           for (int i = 0; i <= 9; i++) {
               result = (result + dp[l][i]) % 1_000_000_000;
           }
 
           System.out.println(result);
          
    }
}
 

 

---

이 문제는 dp로 풀어야 쉽게 풀린다. dp를 생각하지 못하면 굉장히 복잡해진다.

길이가 1인 계단 수의 경우, 1부터 9까지 각 숫자는 1개의 계단 수를 가진다. dp[1][i] = 1로 설정한다.

dp[i][j]는 길이가 i이고 마지막 숫자가 j인 계단 수의 개수를 나타낸다. 

• j == 0일 경우, 이전 길이에서 1로 끝나는 계단 수만 가능
• j == 9일 경우, 이전 길이에서 8로 끝나는 계단 수만 가능

다른 경우는 이전 길이에서 j-1과 j+1로 끝나는 계단 수의 합이다. 

result 변수를 사용해 길이가 l인 모든 계단 수의 총합을 계산한다.결과는 0부터 9까지 dp[l][i]의 합

 

이제 문제가 요구한대로 1,000,000,000 나누면 된다.

 

처음에 dp를 생각하지 못하고 수학적으로 풀려고 접근했었다. 점화식은 생각하지 못했다. 그렇다보니 이상한 l*8+1이라는 결론에 도달해 문제를 풀었는데 실패했다. 그리고 여러가지 시도를 하다가 1시간이 지나버렸고, 답지를 봤는데 이차원 배열의 동적 프로그래밍인걸 보게 되었다. 

 

동적 프로그래밍을 좀 더 공부할 필요가 있어보인다.